Методы искусственного интеллекта для машинного перевода текстов. Роганов В.Р - 31 стр.

грамматику называют грамматикой с самовставлением. Если грамматика G
типа 2 не является грамматикой с самовставлением, то найдется грамматика G′
типа 3, порождающая тот же самый язык. Далее будет описана очень простая
модель автомата, воспринимающего языки типа 3; эта модель непосредственно
определяет структуру программы. Встречаются случаи, когда наиболее очевид-
ная грамматика относится к типу 2 и при ближайшем рассмотрении выясняется,
что она без самовставления. В таких случаях обычно стоит сконструировать
грамматику типа 3 (возможно, интуитивно менее ясную), которая порождает
тот же язык, и использовать ее как руководство при программировании.




           1.6 Конечные автоматы и регулярные языки (типа 3)
     Конечный автомат — эта машина без динамической памяти. Например,
программа на фортране, в которой не используется ленты со стиранием, опре-
деляет конечный автомат, так как у нее нет динамической памяти. Подобным
образом программы на Алголе и ПЛ/1, которые не определяют динамических
структур данных, можно представить как конечные автоматы, так что этот
класс программ имеет немалое практическое значение.
     Язык L воспринимается конечным автоматом тогда и только тогда, ко-
гда L — регулярный язык (типа 3).
     Напомним, что правила регулярного языка имеют вид A → x или A → xB,
где x — терминальный символ, A и B — переменные. Правило A → x можно ин-
терпретировать так:
     Если в состоянии SA читается символ x, то перейти в состояние Sf из F.
     Правило A → xB интерпретируется так:
     Если в состоянии SA читается символ x, то перейти в состояние SВ.
     Эти интерпретации определяют основные блоки для представления ко-
нечного автомата в виде графа.



                                                                         31