Изменения
→Пример:
|id=defambigous
|definition =
'''Неоднозначной грамматикой''' (англ. ''ambiguous grammar'') называется грамматика, в которой можно вывести некоторое слово более чем одним способом (то есть для строки есть более одного [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|дерева разбора]]).
}}
===Пример:===
{{Определение
|definition =
Язык называется '''существенно неоднозначным''' (англ. ''inherently ambiguous language''), если любая грамматика, порождающая его, является неоднозначной.
}}
===Пример:===
Язык <tex>0^a 1^b 2^c</tex>, где либо <tex>a=b</tex>, либо <tex>b=c</tex>, является существенно неоднозначным.
Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists n: 0^n 1^n 2^n</tex> имеет хотя бы <tex>2 </tex> дерева разбора в грамматике <tex>\Gamma</tex>.
Возьмем <tex>k</tex> и рассмотрим слово <tex>0^k 1^k 2^{k+k!}</tex>.
Пометим первые <tex>k</tex> нулей, по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на <tex>5 </tex> частей: <tex>0^k1^k2^{k+k!}=uvxyz</tex>.
Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>y</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>y</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.
== См. также ==
* [[Лемма_Огдена|Лемма Огдена]]* [[Лемма_о_разрастании_для_КС-грамматик|Лемма о разрастании для КС-грамматик]]* [[Теорема_Парика|Теорема Парика]] == Источники информации ==*[http://ru.wikipedia.org/wiki/Алгоритмически_неразрешимая_задача Википедия {{---}} Алгоритмически неразрешимая задача]*[http://en.wikipedia.org/wiki/Ambiguous_grammar Wikipedia {{---}} Ambiguous grammar]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Опровержение контекстно-свободности языка]]
