Является ли данный язык: (обычный | контекстно-свободный | и т. Д.) - PullRequest
Новая
       26

Является ли данный язык: (обычный | контекстно-свободный | и т. Д.)

0 голосов
/ 10 марта 2011

Предположим, E = {a, b}.Пусть L0 = {(b ^ (n)) (a ^ (2n)): n> = 0}.Пусть L = ((НЕ РАБОТАЕТ) L0)

Является ли L регулярным, не зависящим от контекста, но не регулярным или не зависящим от контекста?Докажите свой ответ.

Я ищу, каким будет L, и как его описать аналогично тому, как L0 был описан в вопросе вместе с ответом.

Объяснение очень важно для меня, если вы хотите внести свой вклад, пожалуйста, будьте конкретны.Я хочу понять этот материал для теста.

Большое спасибо!

Ответы [ 2 ]

1 голос
/ 10 марта 2011

Я постараюсь объяснить вам, используя язык непрофессионала и подсказки, чтобы вы могли его формализовать.

L - это язык со всеми строками алфавита E={a,b}, которых нет в языке L0Это не обычный язык.

Строки в L - это все строки, которые заканчиваются в не конечных состояниях DFA L0.Но поскольку вы не можете построить DFA / NFA для L0, у вас также не может быть DFA для L.

Причина: в L0 одно несвязанное число n, которое необходимо сохранить после просмотра всехЗатем используйте b, проверяя a, DFA не имеет памяти.Вы не можете написать регулярное выражение для вышеупомянутого языка.

Использование леммы Pumpping L не является языком без контекста

S = ab - строка в L Использование PL я разделюв 5 частей 

S=uvxyz

u="" v=a x="" y=b z=""

Теперь для n=0 новая строка будет S(n=0)="" which is not in L.

, если мы разделим ab на 

   u="" v="" x=a y=b z=""

Теперь дляn=2 S(n=2)=abb which is not in L

Так что L не является CFG.

PS: Дайте мне знать, если вы найдете какое-либо отверстие в m

0 голосов
/ 11 марта 2011

Я не уверен, что ты выучил лему прокачки. Но это способ сказать, является ли язык регулярным. И помните, что если L0 является регулярным, то L1 также является регулярным, поскольку вы можете сделать dfa из L1, поменяв местами окончательную и начальную статистику L0 dfa.

Содержит любой пример L0, где b ^ m a ^ 2m, и эта строка достаточно велика для прокачки лемы.

Разделите пример на три части xyz.

где | xy | = 1.

Так как кусок xy

теперь позволяет качать y 0 раз.

x y ^ 0 z имеет, поэтому, если ваш lang был bbbaaaaaa и | y | = 1, ваш lang становится bbaaaaaa, что означает, что теперь он следует за b ^ n a ^ 3n. Что делает его не регулярным выражением.

Это означает, что L1 не является регулярным выражением 2.

...