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

     Таким образом, КС–грамматика тогда и только тогда является линейной,
когда правая часть каждого ее правила содержит не более одного вхождения
вспомогательного символа.
     Определение. Правило называется праволинейным (леволинейным), если
оно имеет вид ξ → u или ξ → uν (ξ → ν u), где u ∈ Σ* и ν ∈ V — Σ.       КС–
грамматика называется праволинейной (леволинейной), если каждое ее правило
является праволинейным (леволинейным).
     Пример. Грамматика G = (V, {a, b, c}, P,), где P = {σ → abσ, σ → сν, ν →
baν, ν → a}, является праволинейной.
     Очевидно, что всякое праволинейное правило является линейным.
     Теорема. Множество тогда и только тогда является регулярным, когда
оно порождается некоторой праволинейной КС–грамматикой.
     Теорема. Каждое регулярное множество является определенным КС–
языком.
     Теперь мы введем семейство недетерминированных автоматов, которые
допускают в точности все КС–языки и находятся, таким образом, в том же от-
ношении с последними, в каком конечные автоматы стоят к нерегулярным
множествам. Такие автоматы, называемые автоматами с магазинной памя-
тью, или, сокращенно, МП–автоматами, неформально могут быть описаны
следующим образом. Автомат имеет конечное множество состояний, конеч-
ное множество входных символов и неограниченную справа вспомогательную
ленту (называемую лентой магазинной памяти, или магазинной памятью).
Кроме того, он имеет начальное состояние, начальный вспомогательный сим-
вол (вспомогательными символами называются символы, записываемые в мага-
зинной памяти) и некоторое множество заключительных состояний.
     В общем случае автомат, находясь в некотором состоянии, читает вход-
ной символ, или ε, и в качестве самого правого символа в магазинной памяти
имеет символ Z.



                                                                           17