Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 42 стр.

                                                                                            42
самовложения,         эквивалентна     регулярной         грамматике         и    генерирует
регулярный язык. С другой стороны, регулярная грамматика не может
содержать самовложения. Именно самовложение позволяет эффективно
различать КС (нерегулярные) и регулярные языки. Как видно из второго
примера, согласование скобок и т.п. требует самовложения, поэтому его
нельзя специфицировать посредством регулярной грамматики.
      С точки зрения разбора важно, что КС язык в состоянии распознавать
автомат магазинного типа, эквивалентный конечному автомату, к которому
добавлена память магазинного типа (стек). В функции автомата магазинного
типа входит:
      а) чтение входного символа, замещение верхнего символа стека
строкой символов (возможно, пустой) и изменение состояния или
      б) все то же самое, но без чтения входного символа.
      Автомат магазинного типа можно представить кратным
      (K, S, Г, δ, S0 , Z0 ),
      где K – конечное множество состояний, S – входной алфавит, Г –
алфавит магазинный, δ – множество переходов, S0 – начальное состояние, Z0
– символ магазина, который первоначально находится в стеке.
      Рассмотрим, например, автомат магазинного типа М, определенный
следующим образом:
      K = {A},                                            S0 ={A},
      S = { '(' , ')'},                                   Z0 = I.
      Г = {O, I},
      δ задается как δ (A, I, '(') = (A, IO)
(что означает: в состоянии A с I в вершине стека при чтении '(' перейти к
состоянию A и заменить I на IO).
δ (A, O, '(') = (A, OO),        δ (A, O, ')') = (A, ε),              δ(A, I, ε) = (A, ε).
      Автомат М распознает согласуемые пары скобок. Открывающие скобки
(представляемые как O) помещаются в стек и удаляются оттуда, когда
встречается       соответствующая       закрывающая          скобка.       Строка      скобок