Характеризация праволинейных языков

Теорема 2.4.1. Каждый автоматный язык является праволинейным.

Без ограничения общности можно предположить, что исходный язык задан конечным автоматом , где и I = {q₀}. Положим N = Q, S = q₀ и

Пример 2.4.2. Язык, распознаваемый конечным автоматом из примера 2.1.2, порождается грамматикой

Теорема 2.4.3. Каждый праволинейный язык является автоматным.

Доказательство. Без ограничения общности можно предположить, что исходный язык задан праволинейной грамматикой, не содержащей правил вида , где . Положим Q = N, I = {S}, и .

Пример 2.4.4. Пусть . Рассмотрим грамматику

Она эквивалентна грамматике

Язык, порождаемый этими грамматиками, распознается конечным автоматом , где Q = {S,T,E}, I = {S}, F = {E} и

Упражнение 2.4.5. Найти праволинейную грамматику, порождающую язык

Упражнение 2.4.6. Существует ли такая праволинейная грамматика G, что язык L(G)^R не порождается ни одной праволинейной грамматикой, имеющей столько же правил, сколько грамматика G?

Упражнение 2.4.7. Существует ли такая праволинейная грамматика G, что язык L(G)^R не порождается ни одной праволинейной грамматикой с количеством правил n + 1, где n - количество правил в грамматике G?

Упражнение 2.4.8. Существует ли такая праволинейная грамматика G с тремя вспомогательными символами, что язык L(G)^R не порождается ни одной праволинейной грамматикой с тремя вспомогательными символами?