Теорема. Связь рациональных языков с языками, порождаемыми праволинейными грамматиками

Язык рационален $\iff$ он порождается праволинейной грамматикой

Доказательство

Необходимость

Множество нетерминалов строящейся грамматики совпадает с множеством состояний автомата

Достаточность

Вспомогательное утверждения для доказательства:

То есть преобразовали грамматику так, чтобы в правых частях ее правил не осталось цепочек, состоящих только из терминальных символов.

Само доказательство

Почему полученный автомат не обязательно является ДКА?

Полученный автомат в общем случае является НКА из-за возможности существования альтернативных правил в исходной грамматике. Например, праволинейной грамматике. К тому же для заключительных состояний может быть не задана функция перехода.

$$G=\{S\to aA|aB,A\to ϵ,B\to ϵ\}$$

Будет соответствовать НКА:

	$a$	F
$S$	$A,B$	0
$A$	$\varnothing$	1
$B$	$\varnothing$	1

---

Связанные теоремы/определения

• Рациональный язык
• Грамматика
• КС
• Детерменированный конечный автомат