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

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

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

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

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

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

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

Шин Е.Д.

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

2002

Построить детерминированный конечный автомат по автоматной грамматике G.

T={a,b}

N={S,A,B,C}

R={SaA, SbB, AaA, A, AbB, BaC, C, CaC}

1. Исключим -правила.

G`=<T,N,S,R`>

R`={SaA, Sa, SbB, AaA, Aa, AbB, BaC, Ba, CaC, Ca }

2. Построим автомат.

Q={S,A,B,C,E}

={a,b}

={таблица}

q₀=S

F={E}

3. Построим диаграмму.

a a

a

b

b b a a

a

a

4. Построим таблицу по диаграмме, получается не детерминированный автомат.

	A	b
S	A,E	B
A	A,E	B
B	C,E
C	C,E
E	E	E

5. Построим детерминированный автомат, для этого введем новые состояния.

Обозначим q₀=A,E; q₁=B; q₂=C,E

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

={a,b}

={таблица}

q₀

F={q₀, q₂}

	a	b
q0	q0	q1
q1	q2
q2	q2

Автоматом распознается язык, состоящий из следующих цепочек.

aaa…aaa

или

aaa…aaabaa…aaa

0..m 1..n

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

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

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

Сеанс : 14.10.02 , 23:18 .

Файл : "LIST1.TXT" .

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

a a a b a a a a a Eps

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

q0 q1 q2

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

Детерминированный Конечный Автомат

УПРАВЛЯЮЩАЯ ТАБЛИЦА :

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

| |a | b | Eps|

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

| q0 |q0 |q1 | |

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

| q1 |q2 | | |

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

| q2 |q2 | | |

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

Примеры работы автомата.

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

a a a b a a a a Eps

# ¦Тек.состояние ¦ Вх. цепочка

0¦ q0 ¦ a a a

1¦ q0 ¦ a a b

2¦ q0 ¦ a b a

3¦ q0 ¦ b a a

4¦ q1 ¦ a a a

5¦ q2 ¦ a a a

6¦ q2 ¦ a a Eps

7¦ q2 ¦ a Eps

8¦ q2 ¦ Eps

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

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

b a a a a Eps

# ¦Тек.состояние ¦ Вх. цепочка

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

0¦ q0 ¦ b a a

1¦ q1 ¦ a a a

2¦ q2 ¦ a a a

3¦ q2 ¦ a a Eps

4¦ q2 ¦ a Eps

5¦ q2 ¦ Eps

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

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

a a a a Eps

# ¦Тек.состояние ¦ Вх. цепочка

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

0¦ q0 ¦ a a a

1¦ q0 ¦ a a a

2¦ q0 ¦ a a Eps

3¦ q0 ¦ a Eps

4¦ q0 ¦ Eps

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

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

b b a a b b Eps

# ¦Тек.состояние ¦ Вх. цепочка

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

0¦ q0 ¦ b b a

1¦ q1 ¦ b a a

2¦ q1 ¦ b a a

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

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

a a a a b Eps

# ¦Тек.состояние ¦ Вх. цепочка

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

0¦ q0 ¦ a a a

1¦ q0 ¦ a a a

2¦ q0 ¦ a a b

3¦ q0 ¦ a b Eps

4¦ q0 ¦ b Eps

5¦ q1 ¦ Eps

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

2. Целые числа заданы последовательностью символов «/» (количество символов «/» определяет значение числа). Определить детерминированный конечный преобразователь, преобразующий последовательность таких чисел в цепочку aⁿ, где n – число нечетных чисел. Числа разделяются запятой, последовательность заканчивается точкой.

Пример:

Вход: //////,/////////,//////,///////,///,/.

Выход: aaaa

1. Построим преобразователь.

M={Q, , , , q, F}

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

={/, , , .}

={a}

={таблица}

q₀

F={q₂}

Построим диаграмму.

./a / , /a

/

.

,

	/	,	.
q0	q1/	q0/	q2/
q1	q0/	q0 / a	q2/ a
q2

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

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

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

Сеанс : 15.10.02 , 0:13 .

Файл : "LAB2LIST.TXT" .

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

/ / / / / , / / , / / / . Eps

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

q0 q1 q2

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

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

УПРАВЛЯЮЩАЯ ТАБЛИЦА :

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

| | / | , | . |Eps|

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

| q0 |q1 |q0 |q2 | |

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

| q1 |q0 |q0 |q2 | |

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

| q2 | | | | |

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

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

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

Вывод(q1 , . )= a