Дешифруемость языков грамматик и автоматов

16

Обратите внимание, что это вопрос, связанный с обучением на курсе CS в университете, это НЕ домашняя работа, и его можно найти здесь под экзаменом осень 2011 года2.

Вот два вопроса, на которые я смотрю с прошлого экзамена. Похоже, они связаны, первое:

Позволять

FINITECFG={<G>∣G is a Context Free Grammar with |L(G)|<}

Докажите, что FINITECFG является разрешимым языком.

и...

Позволять

FINITETM={<M>∣M is a Turing Machine with |L(M)|<}

Докажите, что FINITETM - неразрешимый язык.

Я немного растерялся, как решать эти проблемы, но у меня есть несколько идей, которые, я думаю, могут быть в правильном направлении. Первое, что мне известно, это то, что язык , гдеAREX

AREX={<R,w>∣R is a regular expression with wL(R)}

является разрешимым языком (доказательство в теории вычислений Майкла Сипсера , стр. 168). Тот же источник также доказывает, что контекстно-свободная грамматика может быть преобразована в регулярное выражение, и наоборот. Таким образом, также должен быть разрешимым, поскольку его можно преобразовать в регулярное выражение. Это, а также тот факт , что Т М являетсяACFGATM ипом -разрешимого, по- видимому, связан с этой проблемой.

Единственное , что можно думать о прохождении G Тьюрингу машиной для (после преобразования G с регулярным выражением) и Т М . Затем принять, если G делает, и отклонить, если G нет. Как A T MAREXATMATM неразрешимо, этого никогда не произойдет. Почему-то мне кажется, что я здесь ошибаюсь, но я не уверен, что это такое. Может ли кто-нибудь помочь мне здесь?

BrotherJack
источник
5
«Контекстно-свободная грамматика может быть преобразована в регулярное выражение, и наоборот». Это неправда (если вы не интерпретируете ее как «существует CFG, который можно преобразовать в регулярное выражение», но я не думаю, что это то, что вы означало). Регулярные грамматики могут быть преобразованы в регулярные выражения. Не существует алгоритма преобразования CFG в регулярные выражения по той простой причине, что большинство контекстно-свободных языков (то есть все контекстно-свободные языки, которые также не являются регулярными языками) не могут быть описаны с помощью регулярных выражений.
sepp2k

Ответы:

9
  1. Перевести Г в нормальную форму Хомского . Таким образом, единственным пустым производным будет начальный символ, который больше нигде не появляется, и, таким образом, если есть какое-то произведение, которое может в конечном итоге генерировать себя, то грамматика бесконечна. Если такого производства не существует, каждый символ сможет генерировать только конечный набор строк, и тогда грамматика будет конечной. Итак, создайте ориентированный граф, в котором каждое производство является узлом, а каждый символ внутри производства является ребром, нацеленным на этот символ. Если у графа есть некоторый цикл, CFG бесконечен, иначе это не так. Следовательно, машина Тьюринга для может быть построена именно так, и тогда F IFINITECFGFINITECFG разрешима.

  2. FINITETMHFINITETMFINITETMHH принимает входные данные, что приводит к противоречию, поскольку входной набор бесконечен (длина входных данных не ограничена, поэтому принимайте любую возможную строку в качестве ввода означает принятие бесконечного набора строк). ЕслиFINITETMHH rejects the input, meaning that H's language is finite because it does not accepts any input (i.e. its language is empty), which leads to a contradiction too. This way, the supposition that H exists leads to contradiction, and this supposition is based in the supposition that FINITETM is decidable. So, by contradiction, we have that FINITETM is not decidable.

The same source also proves that a Context Free Grammar can be converted to a regular expression, and vice versa.

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.

Victor Stafusa
источник
1
I'm having some problem following proof two . OK so you pass H to G, yes? If G returns true than H is finite, that makes sense. However, I don't get the input set being infinite, what is the input you are referrng to?
BrotherJack
1
@BrotherJack The H's input might be of any length, its length is unbounded. It could be a string with just one symbol or it could be a million terabyte long input. This way, the possible inputs for H are an infinite set because we can make it arbitrarily large.
Victor Stafusa
1
OK. That seems to make sense. Would it be accurate to refer to that input as "any possible string within the input language H"?
BrotherJack
1
@BrotherJack - I edited the answer to make that point clearer.
Victor Stafusa
1
Excellent explaination! Thank you very much for your time.
BrotherJack
2

Another way to decide FINITECFG is via the pumping lemma.

The pumping lemma says that each CFL L 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 xL which is longer than N can be "pumped".

This means that if L is finite, all the words in L are shorter than N.

Now, all that one needs to check is words with lengths between N 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.

Ran G.
источник