Существенно неоднозначные языки — различия между версиями
(→Пример:) |
м (rollbackEdits.php mass rollback) |
||
(не показано 30 промежуточных версий 9 участников) | |||
Строка 1: | Строка 1: | ||
== Неоднозначные грамматики == | == Неоднозначные грамматики == | ||
{{Определение | {{Определение | ||
+ | |id=defambigous | ||
|definition = | |definition = | ||
− | '''Неоднозначной грамматикой''' называется грамматика, в которой можно вывести некоторое слово более чем одним способом (то есть для строки есть более одного дерева разбора). | + | '''Неоднозначной грамматикой''' (англ. ''ambiguous grammar'') называется грамматика, в которой можно вывести некоторое слово более чем одним способом (то есть для строки есть более одного [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|дерева разбора]]). |
}} | }} | ||
===Пример:=== | ===Пример:=== | ||
Строка 12: | Строка 13: | ||
Эта грамматика неоднозначна. | Эта грамматика неоднозначна. | ||
+ | |||
+ | В данном случае мы нашли пример слова из языка (который задается грамматикой), которое имеет более одного вывода, и показали, что грамматика является существенно неоднозначной. Однако в общем случае проверка грамматики на неоднозначность является [[Примеры неразрешимых задач: однозначность грамматики|алгоритмически неразрешимой задачей]]. | ||
== Существенно неоднозначные языки == | == Существенно неоднозначные языки == | ||
Строка 17: | Строка 20: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | Язык называется '''существенно неоднозначным''', если | + | Язык называется '''существенно неоднозначным''' (англ. ''inherently ambiguous language''), если любая грамматика, порождающая его, является неоднозначной. |
}} | }} | ||
===Пример:=== | ===Пример:=== | ||
Строка 23: | Строка 26: | ||
Язык <tex>0^a 1^b 2^c</tex>, где либо <tex>a=b</tex>, либо <tex>b=c</tex>, является существенно неоднозначным. | Язык <tex>0^a 1^b 2^c</tex>, где либо <tex>a=b</tex>, либо <tex>b=c</tex>, является существенно неоднозначным. | ||
− | Докажем, что для любой грамматики <tex>\Gamma</tex> <tex>\exists | + | Докажем, что для любой грамматики <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>0^k 1^k 2^{k+k!}</tex>. | ||
− | Пометим первые <tex>k</tex> нулей, по [[Лемма Огдена|лемме Огдена]] данное слово можно разбить на 5 частей: <tex>0^k1^k2^{k+k!}=uvxyz</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> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку. | Понятно, что <tex>v</tex> состоит полностью из нулей, а <tex>y</tex> состоит полностью из единиц, а также длины <tex>v</tex> и <tex>y</tex> равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку. | ||
− | Пусть <tex>|v|=|y|=t</tex>, тогда возьмём слово <tex>q=uv^{ | + | Пусть <tex>|v|=|y|=t</tex>, тогда возьмём слово <tex>q=uv^{k! / t + 1}xy^{k! / t + 1}z</tex>. По лемме Огдена слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>A</tex> такой, что с помощью него можно породить слово <tex>q</tex>, то есть в грамматике можно вывести <tex>uAz</tex>, и из <tex>A</tex> можно вывести <tex>vAy</tex> и <tex>x</tex>. (Заметим, что <tex>q = 0^{k! + k}1^{k! + k}2^{k! + k}</tex>, то есть <tex>n = k! + k</tex>.) |
[[Файл:TreeA.png]] | [[Файл:TreeA.png]] | ||
− | Теперь рассмотрим слово <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>B</tex> такой, что с помощью него можно породить слово <tex>q</tex>. | + | Теперь рассмотрим слово <tex>0^{k+k!} 1^k 2^k</tex>, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово <tex>q</tex> принадлежит языку, а также существует нетерминал <tex>B</tex> такой, что с помощью него можно породить слово <tex>q</tex>, где <tex>|v|=|y|=p</tex>. |
[[Файл:TreeB.png]] | [[Файл:TreeB.png]] | ||
− | + | Заметим, что поддеревья, соответствующие <tex>A</tex> и <tex>B</tex> {{---}} разные деревья и одно не является потомком другого, иначе или в поддереве <tex>A</tex> были бы двойки, или в поддереве <tex>B</tex> были бы нули {{---}} что не является правдой. | |
+ | |||
+ | |||
+ | Пусть в этих двух случаях дерево разбора было одно и тоже, тогда с помощью <tex>A</tex> и <tex>B</tex> можно породить слово вида <tex>0^{k+k!+t} 1^{k+k!+t+p} 2^{k+k!+p}</tex>, которое не принадлежит языку. | ||
+ | |||
+ | В результате мы имеем два [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|дерева разбора]] для одного слова. Значит, язык существенно неоднозначен. | ||
+ | == См. также == | ||
+ | * [[Лемма_Огдена|Лемма Огдена]] | ||
+ | * [[Лемма_о_разрастании_для_КС-грамматик|Лемма о разрастании для КС-грамматик]] | ||
+ | * [[Теорема_Парика|Теорема Парика]] | ||
− | + | == Источники информации == | |
+ | *[http://ru.wikipedia.org/wiki/Алгоритмически_неразрешимая_задача Википедия {{---}} Алгоритмически неразрешимая задача] | ||
+ | *[http://en.wikipedia.org/wiki/Ambiguous_grammar Wikipedia {{---}} Ambiguous grammar] | ||
− | + | [[Категория: Теория формальных языков]] | |
+ | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Опровержение контекстно-свободности языка]] |
Текущая версия на 19:38, 4 сентября 2022
Неоднозначные грамматики
Определение: |
Неоднозначной грамматикой (англ. ambiguous grammar) называется грамматика, в которой можно вывести некоторое слово более чем одним способом (то есть для строки есть более одного дерева разбора). |
Пример:
Рассмотрим грамматику
и выводимое слово . Его можно вывести двумя способами:
Эта грамматика неоднозначна.
В данном случае мы нашли пример слова из языка (который задается грамматикой), которое имеет более одного вывода, и показали, что грамматика является существенно неоднозначной. Однако в общем случае проверка грамматики на неоднозначность является алгоритмически неразрешимой задачей.
Существенно неоднозначные языки
Определение: |
Язык называется существенно неоднозначным (англ. inherently ambiguous language), если любая грамматика, порождающая его, является неоднозначной. |
Пример:
Язык
, где либо , либо , является существенно неоднозначным.Докажем, что для любой грамматики
имеет хотя бы дерева разбора в грамматике .Возьмем
и рассмотрим слово .Пометим первые лемме Огдена данное слово можно разбить на частей: .
нулей, поПонятно, что
состоит полностью из нулей, а состоит полностью из единиц, а также длины и равны, так как иначе при накачке мы можем получить слово, не принадлежащее языку.Пусть
, тогда возьмём слово . По лемме Огдена слово принадлежит языку, а также существует нетерминал такой, что с помощью него можно породить слово , то есть в грамматике можно вывести , и из можно вывести и . (Заметим, что , то есть .)Теперь рассмотрим слово
, в котором отмечены все двойки. Аналогичными рассуждениями мы получаем, что слово принадлежит языку, а также существует нетерминал такой, что с помощью него можно породить слово , где .Заметим, что поддеревья, соответствующие
и — разные деревья и одно не является потомком другого, иначе или в поддереве были бы двойки, или в поддереве были бы нули — что не является правдой.
Пусть в этих двух случаях дерево разбора было одно и тоже, тогда с помощью и можно породить слово вида , которое не принадлежит языку.
В результате мы имеем два дерева разбора для одного слова. Значит, язык существенно неоднозначен.