Теория автоматов. - 11 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Рубрика: 

8. Минимизировать автомат Мура.
8.1* Таблица 44 8.2* Таблица 45
9. Синтезировать распознающий автомат, описываемы регулярной
(автономной) грамматикой.
9.1.*На вход могут поступать символы, допустимые в языке ПЛ/1. Авто-
мат распознаёт идентификаторы (без ограничения по длинне).
9.2.*Автомат распознаёт десятичные константы с фиксированной точ-
кой, допустимые в ПЛ/1.
9.5.*Автомат распознаёт условный оператор ПЛ/1 , которыё имеет вид:
IF е THEN t
1
[ELSE t
2
]
Считаем, что на этом этапе анализа ключевые слова языка, а также вы-
ражения е и группы операторов t
1
и t
2
заменены отдельными символами.
Квадратные скобки говорят о том, что соответствующий фрагмент может отсут-
ствовать.
11.. Для недетерминированного автомата, заданного грамматическими
правилами, построить эквивалентный детерминированный автомат.
11.1.* А ::= ab / aC 11.2. A ::= ab / bB / aC
B ::= b B ::= bc / b
C ::= a C ::= a
12. Придумать свои упражнения, аналогичные приведённым, и выпол-
нить их.
РЕШЕНИЯ.
1.1. Соответствующий автомат Мура представлен на рис. 8.
Рис. 8
y
1
y
2
y
1
y
1
y
1
y
1
y
2
1 2 3 4 5 6 7
x
1
1 2 3 4 1 2 1
x
2
5 5 5 2 7 2 2
y
1
y
1
y
2
y
2
y
1
y
1
y
2
a b c d e f g
x
1
d g g d d c g
x
2
a b b b b a b
x
3
e b b g g d d 
        8. Минимизировать автомат Мура.

        8.1*           Таблица 44            8.2*           Таблица 45

         y1 y2 y1 y1 y1 y1 y2                       y1 y1 y2 y2 y1 y1 y2
         1     2   3   4   5   6    7               a   b    c   d   e   f   g
   x1    1     2   3   4   1   2    1          x1   d   g    g   d   d   c   g
   x2    5     5   5   2   7   2    2          x2   a   b    b   b   b   a   b
                                               x3   e   b    b   g   g   d   d



       9. Синтезировать распознающий автомат, описываемы регулярной
(автономной) грамматикой.
       9.1.*На вход могут поступать символы, допустимые в языке ПЛ/1. Авто-
мат распознаёт идентификаторы (без ограничения по длинне).
       9.2.*Автомат распознаёт десятичные константы с фиксированной точ-
кой, допустимые в ПЛ/1.
       9.5.*Автомат распознаёт условный оператор ПЛ/1 , которыё имеет вид:
                        IF е THEN t1 [ELSE t2]
       Считаем, что на этом этапе анализа ключевые слова языка, а также вы-
ражения е и группы операторов t1 и t2 заменены отдельными символами.
Квадратные скобки говорят о том, что соответствующий фрагмент может отсут-
ствовать.

      11.. Для недетерминированного автомата, заданного грамматическими
правилами, построить эквивалентный детерминированный автомат.
      11.1.* А ::= ab / aC                  11.2. A ::= ab / bB / aC
              B ::= b                             B ::= bc / b
              C ::= a                             C ::= a

       12.     Придумать свои упражнения, аналогичные приведённым, и выпол-
нить их.


                                    РЕШЕНИЯ.

        1.1. Соответствующий автомат Мура представлен на рис. 8.




                                    Рис. 8

Страницы