Математическая теория формальных языков
Однозначные праволинейные грамматики
Теорема 7.3.1.
Каждый праволинейный язык порождается некоторой однозначной праволинейной грамматикой. Другими словами, ни один праволинейный язык не является существенно неоднозначным.
Доказательство. Согласно теоремам 2.4.3 и 2.7.1 исходный язык распознается некоторым детерминированным конечным автоматом. Применив к нему конструкцию из доказательства теоремы 2.4.1, получим однозначную праволинейную грамматику.
Замечание 7.3.2.
Этот факт можно получить также из более общей теоремы 12.2.6 с учетом теоремы 12.2.1.
Упражнение 7.3.3. Найти однозначную праволинейную грамматику, порождающую язык a*((a+b)(a+b))*b*.
Упражнение 7.3.4. Найти однозначную праволинейную грамматику, эквивалентную грамматике
Упражнение 7.3.5. Найти однозначную праволинейную грамматику, эквивалентную грамматике
Упражнение 7.3.6. Существует ли праволинейная грамматика в нормальной форме с n вспомогательными символами, не эквивалентная ни одной однозначной праволинейной грамматике с количеством вспомогательных символов 2n - 1?
