Jump to content

Курода нормальная форма

В теории формального языка находится несжимающая грамматика в нормальной форме Курода, если все правила производства имеют вид: [1]

AB CD или
А БК или
А Б или
А а

где A, B, C и D — нетерминальные символы, а a терминальный символ . [1] отсутствует В некоторых источниках шаблон A B . [2]

Она названа в честь Сиге-Юки Курода , который первоначально назвал ее линейной ограниченной грамматикой , терминология, которая впоследствии также использовалась несколькими другими авторами. [3]

Каждая грамматика в нормальной форме Курода является несжимающей и, следовательно, порождает контекстно-зависимый язык . И наоборот, каждую несжимающую грамматику, которая не генерирует пустую строку, можно преобразовать в нормальную форму Курода. [2]

Простой метод, приписываемый Дьёрдь Ревесу, преобразует грамматику в нормальной форме Курода в контекстно-зависимую грамматику : AB CD заменяется четырьмя контекстно-зависимыми правилами AB AZ , AZ WZ , WZ WD и WD CD . Это доказывает, что каждая несжимающая грамматика порождает контекстно-зависимый язык. [1]

Существует аналогичная нормальная форма для неограниченных грамматик , которую, по крайней мере, некоторые авторы также называют «нормальной формой Курода»: и [4]

AB CD или
А БК или
А а или
А е

где ε — пустая строка. Любая неограниченная грамматика слабо эквивалентна грамматике, использующей только произведения этой формы. [2]

Если исключить правило AB → CD из приведенного выше, можно получить контекстно-свободные грамматики в нормальной форме Хомского . [5] ( Нормальная форма Пенттонена для неограниченных грамматик) — это особый случай, когда первое правило выше — AB AD . [4] Аналогично, для контекстно-зависимых грамматик нормальная форма Пенттонена, также называемая односторонней нормальной формой (следуя собственной терминологии Пенттонена), имеет вид: [1] [2]

AB AD или
А БК или
А а

Для каждой контекстно-зависимой грамматики существует слабо эквивалентная односторонняя нормальная форма. [2]

См. также

[ редактировать ]
  1. ^ Jump up to: а б с д Масами Ито; Юдзи Кобаяши; Кунитака Сёдзи (2010). Автоматы, формальные языки и алгебраические системы: материалы AFLAS 2008, Киото, Япония, 20-22 сентября 2008 г. Всемирная научная. п. 182. ИСБН  978-981-4317-60-3 .
  2. ^ Jump up to: а б с д и Матееску, Александру; Саломаа, Арто (1997). «Глава 4: Аспекты классической теории языка». В Розенберге, Гжегоже; Саломаа, Арто (ред.). Справочник формальных языков. Том I: Слово, язык, грамматика . Спрингер-Верлаг. п. 190. ИСБН  978-3-540-61486-9 .
  3. ^ Виллем Дж. М. Левельт (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. стр. 126–127. ISBN  978-90-272-3250-2 .
  4. ^ Jump up to: а б Александр Медуна (2000). Автоматы и языки: теория и приложения . Springer Science & Business Media. п. 722. ИСБН  978-1-85233-074-3 .
  5. ^ Александр Медуна (2000). Автоматы и языки: теория и приложения . Springer Science & Business Media. п. 728. ИСБН  978-1-85233-074-3 .

Дальнейшее чтение

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 3f25337b305fefbd5dbc3581dbfec55b__1685026920
URL1:https://arc.ask3.ru/arc/aa/3f/5b/3f25337b305fefbd5dbc3581dbfec55b.html
Заголовок, (Title) документа по адресу, URL1:
Kuroda normal form - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)