Курода нормальная форма
В теории формального языка находится несжимающая грамматика в нормальной форме Курода, если все правила производства имеют вид: [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]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б с д Масами Ито; Юдзи Кобаяши; Кунитака Сёдзи (2010). Автоматы, формальные языки и алгебраические системы: материалы AFLAS 2008, Киото, Япония, 20-22 сентября 2008 г. Всемирная научная. п. 182. ИСБН 978-981-4317-60-3 .
- ^ Jump up to: а б с д и Матееску, Александру; Саломаа, Арто (1997). «Глава 4: Аспекты классической теории языка». В Розенберге, Гжегоже; Саломаа, Арто (ред.). Справочник формальных языков. Том I: Слово, язык, грамматика . Спрингер-Верлаг. п. 190. ИСБН 978-3-540-61486-9 .
- ^ Виллем Дж. М. Левельт (2008). Введение в теорию формальных языков и автоматов . Издательство Джона Бенджамина. стр. 126–127. ISBN 978-90-272-3250-2 .
- ^ Jump up to: а б Александр Медуна (2000). Автоматы и языки: теория и приложения . Springer Science & Business Media. п. 722. ИСБН 978-1-85233-074-3 .
- ^ Александр Медуна (2000). Автоматы и языки: теория и приложения . Springer Science & Business Media. п. 728. ИСБН 978-1-85233-074-3 .
Дальнейшее чтение
[ редактировать ]- Сиге-Юки Курода (июнь 1964 г.). «Классы языков и линейно-ограниченные автоматы» . Информация и контроль . 7 (2): 207–223. дои : 10.1016/S0019-9958(64)90120-2 .
- Г. Ревес, «Комментарий к статье «Обнаружение ошибок в формальных языках», Journal of Computer and System Sciences, vol. 8, нет. 2, стр. 238–242, апрель 1974 г. doi : 10.1016/S0022-0000(74)80057-7 (трюк Ревеса)
- Пенттонен, Мартти (август 1974 г.). «Односторонний и двусторонний контекст в формальных грамматиках» . Информация и контроль . 25 (4): 371–392. дои : 10.1016/S0019-9958(74)91049-3 .