Лабораторные работы 1-7(старые) / Отчет по ТЯП4

Санкт-Петербургский государственный электротехнический университет

КАФЕДРА МО ЭВМ

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ N4

по дисциплине "Теория языков программирования"

“Автоматы и преобразователи с магазинной памятью.”

Преподаватель: Самойленко В.П.

студенты гр. 0341 Юбрин А.Н.

Шин Е.Д.

Санкт-Петербург

2002

4.1.1 Построить детерминированный магазинный автомат, распознающий цепочки из множества {aⁿb^mcⁿ, где n>0, m>=0}.

1. Автомат с магазинной памятью G=<Q,  q₀, Z₀, F>

Q={q₀, q₁, q₂ q₃}.

{a,b,c}

Г={a}

<q₀, a, Z>= (q₁, a);

<q₁, a, a>= (q₁, aa); <q₁, b, a>= (q₂, a); <q₁, c, a>= (q₂, );

<q₂, b, a>= (q₂, a); <q₂, c, a>= (q₃, );

<q₃, c, a>= (q₁, ); <q₃, , Z>= (q₀, );

Автоматом распознается язык из множества {aⁿb^mcⁿ, где n>0, m>=0}.

Л А Б О Р А Т О Р Н А Я Р А Б О Т А # 4

" Распознаватели и преобразователи "

Студент : ШИН.ЮБРИН , группа : 0341 .

Сеанс : 20.10.02 , 17:50 .

Файл : "LIST4.TXT" .

ВХОДНАЯ ЦЕПОЧКА ( количество элементов : 9 ) :

a a a b b c c c Eps

МНОЖЕСТВО СОСТОЯНИЙ ( количество состояний : 4 ) :

q0 q1 q2 q3

Заключительное состояние : q0

Детерминированный МП-Автомат

УПРАВЛЯЮЩАЯ ТАБЛИЦА (для состояния q0 ):

=======================

| |a |b |c |Eps|

=======================

| a | | | | |

|-----|---+---+---+---|

| - |q1 | | | |

=======================

Цепочки замен :

Замена( - ,a )= a

УПРАВЛЯЮЩАЯ ТАБЛИЦА (для состояния q1 ):

=======================

| |a |b |c |Eps|

=======================

| a |q1 |q2 |q3 | |

|-----|---+---+---+---|

| - | | | | |

=======================

Цепочки замен :

Замена(a ,a )= a a

Замена(a ,b )= a

УПРАВЛЯЮЩАЯ ТАБЛИЦА (для состояния q2 ):

=======================

| |a |b |c |Eps|

=======================

| a | |q2 |q3 | |

|-----|---+---+---+---|

| - | | | | |

=======================

Цепочки замен :

Замена(a ,b )= a

УПРАВЛЯЮЩАЯ ТАБЛИЦА (для состояния q3 ):

=======================

| |a |b |c |Eps|

=======================

| a | | |q3 | |

|-----|---+---+---+---|

| - | | | |q0 |

=======================

Цепочки замен :

Примеры.

ВХОДНАЯ ЦЕПОЧКА ( количество элементов : 9 ) :

a a a b b c c c Eps

¦ Конфигурации алгоритма ¦

¦----------------------------------------------------------¦

¦ # ¦ Магазин ¦ Вх. цепочка ¦ Вых. цепочка ¦

¦---+--------------+-----------------+-------------------¦

¦ 0¦ - ¦ a a a ¦ ¦

¦ 1¦ a - ¦ a a b ¦ ¦

¦ 2¦ a a - ¦ a b b ¦ ¦

¦ 3¦ a a a ¦ b b c ¦ ¦

¦ 4¦ a a a ¦ b c c ¦ ¦

¦ 5¦ a a a ¦ c c c ¦ ¦

¦ 6¦ a a - ¦ c c Eps ¦ ¦

¦ 7¦ a - ¦ c Eps ¦ ¦

¦ 8¦ - ¦ Eps ¦ ¦

¦ 9¦ - ¦ Eps ¦ ¦

Разбор входной цепочки завершен успешно !

ВХОДНАЯ ЦЕПОЧКА ( количество элементов : 5 ) :

a a c c Eps

# ¦ Магазин ¦ Вх. цепочка ¦ Вых. цепочка

---+---------------+-----------------+-------------

0¦ - ¦ a a c ¦

1¦ a - ¦ a c c ¦

2¦ a a - ¦ c c Eps ¦

3¦ a - ¦ c Eps ¦

4¦ - ¦ Eps ¦

5¦ - ¦ Eps ¦

Разбор входной цепочки завершен успешно !

ВХОДНАЯ ЦЕПОЧКА ( количество элементов : 8 ) :

a a b b c c c Eps

# ¦ Магазин ¦ Вх. цепочка ¦ Вых. цепочка

---+--------------+-----------------+-------------

0¦ - ¦ a a b ¦

1¦ a - ¦ a b b ¦

2¦ a a - ¦ b b c ¦

3¦ a a - ¦ b c c ¦

4¦ a a - ¦ c c c ¦

5¦ a - ¦ c c Eps ¦

6¦ - ¦ c Eps ¦

7¦ - ¦ c Eps ¦

Входная цепочка заданному языку не принадлежит !

4.2.10 Построить детерминированный преобразователь с магазинной памятью, осуществляющий

перевод цепочек из множества { aⁿb^mcⁿ, где n>0, m>=0} в множество {1^m+n}.

P=<Q, , Г, , , q₀, Z₀, F>

Q={q₀, q₁, q₂ q₃}.

{a,b,c}

Г={a}

={1}

<q₀, a, Z>= (q₁, a, 1);

<q₁, a, a>= (q₁, aa, 1); <q₁, b, a>= (q₂, a, 1); <q₁, c, a>= (q₂, , );

<q₂, b, a>= (q₂, a, 1); <q₂, c, a>= (q₃, , );

<q₃, c, a>= (q₁, , ); <q₃, , Z>= (q₀, , );

Л А Б О Р А Т О Р Н А Я Р А Б О Т А # 1

" Распознаватели и преобразователи "

Студент : П , группа : 4 .

Сеанс : 20.10.02 , 18:25 .

Файл : "LIST41.TXT" .

ВХОДНАЯ ЦЕПОЧКА ( количество элементов : 6 ) :

a a b c c Eps

МНОЖЕСТВО СОСТОЯНИЙ ( количество состояний : 4 ) :

q0 q1 q2 q3

Заключительное состояние : q0

Детерминированный МП-Преобразователь

УПРАВЛЯЮЩАЯ ТАБЛИЦА (для состояния q0 ):

=======================

| |a |b |c |Eps|

=======================

| a | | | | |

|----|---+---+---+---|

| - |q1 | | | |

=======================

Цепочки вывода :

Вывод( - ,a )= 1

Цепочки замен :

Замена( - ,a )= a

УПРАВЛЯЮЩАЯ ТАБЛИЦА (для состояния q1 ):

=======================

| |a |b |c |Eps|

=======================

| a |q1 |q2 |q3 | |

|----|----+---+---+---|

| - | | | | |

=======================

Цепочки вывода :

Вывод(a ,a )= 1

Вывод(a ,b )= 1

Цепочки замен :

Замена(a ,a )= a a

Замена(a ,b )= a

УПРАВЛЯЮЩАЯ ТАБЛИЦА (для состояния q2 ):

=======================

| |a |b |c |Eps|

=======================

| a | |q2 |q3 | |

|-----|---+---+---+---|

| - | | | | |

=======================

Цепочки вывода :

Вывод(a ,b )= 1

Цепочки замен :

Замена(a ,b )= a

УПРАВЛЯЮЩАЯ ТАБЛИЦА (для состояния q3 ):

=======================

| |a |b |c |Eps|

=======================

| a | | |q3 | |

|-----|---+---+---+---|

| - | | | |q0 |

=======================

Цепочки вывода :

Цепочки замен :

Примеры.

ВХОДНАЯ ЦЕПОЧКА ( количество элементов : 6 ) :

a a b c c Eps

# ¦ Магазин ¦ Вх. цепочка ¦ Вых. цепочка

--+----------------+----------------+--------------

0¦ - ¦ a a b ¦

1¦ a - ¦ a b c ¦ 1

2¦ a a - ¦ b c c ¦ 1 1

3¦ a a - ¦ c c Eps ¦ 1 1 1

4¦ a - ¦ c Eps ¦ 1 1 1

5¦ - ¦ Eps ¦ 1 1 1

6¦ - ¦ Eps ¦ 1 1 1

Разбор входной цепочки завершен успешно !

ВХОДНАЯ ЦЕПОЧКА ( количество элементов : 5 ) :

a a c c Eps

# ¦ Магазин ¦ Вх. цепочка ¦ Вых. цепочка

--+---------------+-----------------+--------------

0¦ - ¦ a a c ¦

1¦ a - ¦ a c c ¦ 1

2¦ a a - ¦ c c Eps ¦ 1 1

3¦ a - ¦ c Eps ¦ 1 1

4¦ - ¦ Eps ¦ 1 1

5¦ - ¦ Eps ¦ 1 1

Разбор входной цепочки завершен успешно !

ВХОДНАЯ ЦЕПОЧКА ( количество элементов : 5 ) :

a a b c Eps

# ¦ Магазин ¦ Вх. цепочка ¦ Вых. цепочка

--+---------------+-----------------+-------------

0¦ - ¦ a a b ¦

1¦ a - ¦ a b c ¦ 1

2¦ a a - ¦ b c Eps ¦ 1 1

3¦ a a - ¦ c Eps ¦ 1 1 1

4¦ a - ¦ Eps ¦ 1 1 1

5¦ a - ¦ Eps ¦ 1 1 1

Входная цепочка заданному языку не принадлежит !