Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 39 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

7. Операция пересечения строится в соответствии со следующим преобразованием:
L(A
1
) ∩ L(A
2
) = L(A
1
) ∪ L(A
2
) .
На основании этой теоремы можно строить конечные автоматы, последовательно
синтезируя их на основе уже построенных автоматов.
5.3.4. Автоматные грамматики
Линейные грамматики (праворекурсивные и леворекурсивные) называются автоматными
грамматиками, так как языки, порождаемые ими, совпадают с языками, распознаваемыми
конечными автоматами.
Рассмотрим ряд теорем.
Теорема. Для каждой праволинейной грамматики существует эквивалентный конечный
автомат.
Доказательство. Каждому нетерминалу произвольной праволинейной грамматики G
поставим в соответствие одно состояние конечного автомата A. Добавим еще одно состояние
- единственное конечное состояние. Состояние, соответствующее аксиоме, назовем
начальным состоянием.
Каждому правилу A→aB поставим в соответствие команду Aa → B, а каждому
терминальному правилу A → a поставим в соответствие команду Aa → F.
Таким образом, выводу цепочки в грамматике
S ⇒ a
1
A
1
⇒ a
1
a
2
A
2
⇒ ... ⇒ a
1
a
2
...a
k-1
A
k-1
⇒ a
1
a
2
...a
k
взаимно однозначно соответствует
последовательность команд построенного автомата A:
Aa
1
→ A
1
; A
1
a
2
→ A
2
; . . . ; A
k-1
a
k
→ F. Таким образом, язык L(G) = L(A).
Пример. Пусть для заданной грамматики G требуется построить конечный автомат.
S → aS | bB;
A → aA | bS;
B → bB | с | cA.
Решение. Граф автомата будет иметь четыре вершины, три из них помечены
нетерминальными символами грамматики S, A, B, четвертая вершина, помеченная символом
F, является единственным заключительным состоянием. Начальным состоянием является
вершина, соответствующая аксиоме S.
a b
S
b
B
b
c
c
A F
a
Каждому правилу грамматики поставим в соответствие команду конечного автомата:
Sa → S - в начальном состоянии при поступлении на вход терминального символа а
автомат остается в том же состоянии S;
Sb → B - из начального состояния при поступлении на вход терминала b автомат
переходит в состояние B;
Bb → B - в состоянии В при поступлении на вход терминала b автомат остается в том же
состоянии B; 
   7. Операция пересечения строится в соответствии со следующим преобразованием:

         L(A1) ∩ L(A2) = L(A1) ∪ L(A2) .

    На основании этой теоремы можно строить конечные автоматы, последовательно
синтезируя их на основе уже построенных автоматов.

      5.3.4. Автоматные грамматики
    Линейные грамматики (праворекурсивные и леворекурсивные) называются автоматными
грамматиками, так как языки, порождаемые ими, совпадают с языками, распознаваемыми
конечными автоматами.
    Рассмотрим ряд теорем.
    Теорема. Для каждой праволинейной грамматики существует эквивалентный конечный
автомат.
    Доказательство. Каждому нетерминалу произвольной праволинейной грамматики G
поставим в соответствие одно состояние конечного автомата A. Добавим еще одно состояние
- единственное конечное состояние. Состояние, соответствующее аксиоме, назовем
начальным состоянием.
    Каждому правилу A→aB поставим в соответствие команду Aa → B, а каждому
терминальному правилу A → a поставим в соответствие команду Aa → F.
    Таким образом, выводу цепочки в грамматике
    S ⇒ a1A1 ⇒ a1a2A2 ⇒ ... ⇒ a1a2...ak-1Ak-1⇒ a1a2...ak взаимно однозначно соответствует
последовательность команд построенного автомата A:
    Aa1 → A1; A1a2 → A2; . . . ; Ak-1ak → F. Таким образом, язык L(G) = L(A).
    Пример. Пусть для заданной грамматики G требуется построить конечный автомат.
    S → aS | bB;
    A → aA | bS;
    B → bB | с | cA.
    Решение. Граф автомата будет иметь четыре вершины, три из них помечены
нетерминальными символами грамматики S, A, B, четвертая вершина, помеченная символом
F, является единственным заключительным состоянием. Начальным состоянием является
вершина, соответствующая аксиоме S.
             a                       b
                 S       b   B



                 b
                         c
                                 c
                     A           F
         a




    Каждому правилу грамматики поставим в соответствие команду конечного автомата:
    Sa → S - в начальном состоянии при поступлении на вход терминального символа а
автомат остается в том же состоянии S;
    Sb → B - из начального состояния при поступлении на вход терминала b автомат
переходит в состояние B;
    Bb → B - в состоянии В при поступлении на вход терминала b автомат остается в том же
состоянии B;

Страницы