Обратите внимание, что это вопрос, связанный с обучением на курсе CS в университете, это НЕ домашняя работа, и его можно найти здесь под экзаменом осень 2011 года2.
Вот два вопроса, на которые я смотрю с прошлого экзамена. Похоже, они связаны, первое:
Позволять
Докажите, что является разрешимым языком.
и...
Позволять
Докажите, что - неразрешимый язык.
Я немного растерялся, как решать эти проблемы, но у меня есть несколько идей, которые, я думаю, могут быть в правильном направлении. Первое, что мне известно, это то, что язык , где
является разрешимым языком (доказательство в теории вычислений Майкла Сипсера , стр. 168). Тот же источник также доказывает, что контекстно-свободная грамматика может быть преобразована в регулярное выражение, и наоборот. Таким образом, также должен быть разрешимым, поскольку его можно преобразовать в регулярное выражение. Это, а также тот факт , что Т М является ипом -разрешимого, по- видимому, связан с этой проблемой.
Единственное , что можно думать о прохождении G Тьюрингу машиной для (после преобразования G с регулярным выражением) и Т М . Затем принять, если G делает, и отклонить, если G нет. Как A T M неразрешимо, этого никогда не произойдет. Почему-то мне кажется, что я здесь ошибаюсь, но я не уверен, что это такое. Может ли кто-нибудь помочь мне здесь?
Ответы:
Перевести Г в нормальную форму Хомского . Таким образом, единственным пустым производным будет начальный символ, который больше нигде не появляется, и, таким образом, если есть какое-то произведение, которое может в конечном итоге генерировать себя, то грамматика бесконечна. Если такого производства не существует, каждый символ сможет генерировать только конечный набор строк, и тогда грамматика будет конечной. Итак, создайте ориентированный граф, в котором каждое производство является узлом, а каждый символ внутри производства является ребром, нацеленным на этот символ. Если у графа есть некоторый цикл, CFG бесконечен, иначе это не так. Следовательно, машина Тьюринга для может быть построена именно так, и тогда F IFINITECFG FINITECFG разрешима.
I really doubt that Sipser would state that, you probably misread or misunderstood. This would mean that context-free grammars generate exactly the same langauges as right-linear grammars. This is false; the right-linear grammars generate are a proper subset of the languages context-free grammars dp. That said, the way you tried to use regular languages to answer the questions just leads you to nowhere.
As you can see above in my proofs, the two questions are indeed two very distinct, unrelated questions. It just happens that they were worded similarly.
источник
Another way to decideFINITECFG is via the pumping lemma.
The pumping lemma says that each CFLL has a number N (which can be computed from the grammar, or at least an upper bound of it can easily be computed), such that any x∈L which is longer than N can be "pumped".
This means that ifL is finite, all the words in L are shorter than N .
Now, all that one needs to check is words with lengths betweenN and 2N . If any such word exists, then L is infinite. It is not too difficult to see that this statement is "if and only if", thus if you find no word withing this range, L is finite. The efficiency here is much worse than the answer of Victor, but it teaches something about the structure of CFLs.
источник