Разрешается ли использование CFG с использованием нулевого языка? - PullRequest
Новая
       55

Разрешается ли использование CFG с использованием нулевого языка?

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

Если у меня есть не зависящая от контекста грамматика G, в которой язык G равен нулю, можно ли решить G?

Я знаю, что ответ - да, но мне трудно доказать это.Моя первая мысль состоит в том, чтобы сказать, что есть только одно состояние, q1, которое является начальным состоянием и состоянием принятия для машины Тьюринга, которая эквивалентна G. Эта машина не примет никакого ввода и немедленно остановит и примет, потому что она достигла принятиягосударство.Это приемлемый ответ, или я далеко?

РЕДАКТИРОВАТЬ:

Как сказал Джоэл ниже, язык, который я описал, принимает все строки.Чтобы противостоять этому, я предлагаю вторую машину, G '.G 'имеет 3 состояния, начальное состояние q1, принимающее состояние q2 и отклоненное состояние q3.q1 переходит к q3 по всем символам в алфавите G ', как и q2.q1 имеет эпсилон-переход к q2.Следовательно, если в строке, поданной на G ', есть какие-либо символы, G' отклонит.Если символов нет, единственный вариант - перевести эпсилон-переход в состояние принятия.Как это звучит?

РЕДАКТИРОВАТЬ:

Было доказано, что вышеуказанное решение принимает язык L (G ') = {""}.

1 Ответ

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

Как вы сказали, ответ - да. Общим доказательством является тот факт, что с учетом CFG G вы можете легко (ну вроде) построить TM, имитирующую деривации, используя эту грамматику. Тем не менее, вы ищете краткое доказательство для пустого языка. (Тот факт, что у вас есть CFG в этом случае не имеет значения.)

Вы на правильном пути в том, что если вы можете создать TM, который всегда останавливается для данного языка L, то L разрешима. Однако машина, которую вы описываете, на самом деле будет принимать каждую строку, то есть язык, состоящий из каждой возможной строки в алфавите. Дело в том, что если начальное состояние также является состоянием принятия, то машина Тьюринга примет сразу же при запуске. Он не должен читать всю входную строку (или любую ее часть), чтобы принять.

Чтобы определить TM, который ничего не принимает, пусть набор принимающих состояний будет пустым. Чтобы гарантировать, что ваша машина всегда останавливается, ваша функция перехода также может быть пустой.

...