Название: Информатика (формальные языки и грамматики) - Методическая разработка(С.Е. Рояк)

Жанр: Информатика

Просмотров: 1363


Основные определения

 

1. Детерминированный конечный автомат:

КА = < Q, A, q0, d, F >,

где Q – конечное множество состояний автомата; А – конечное множество входных символов - алфавит автомата;

q0 Î Q, начальное состояние автомата;

d : Q ´ A ® Q – функция перехода; Функция перехода может быть доопределена так: d : Q ´ A* ® Q;

F Ì Q – множество конечных состояний.

2. Язык, допускаемый КА = {x| d(q0, x) Î F, x ÎA* }.

3. Недетерминированный конечный автомат:

НКА = < Q,A,q0, d, F >,

где Q – конечное множество состояний автомата; А – конечное множество входных символов – алфавит автомата;

q0 Î Q, начальное состояние автомата;

d : Q ´ A ® P(Q) – функция перехода, где P(Q) – множество всех подмножеств множества Q; Функция перехода может быть доопределена так d: Q ´ A* ® Р(Q);

F Ì Q – множество конечных состояний.

4. Язык, допускаемый НКА = {x| d(q0, x) Ç F¹ Æ, x ÎA* }.

5. Алгоритм преобразования НКА в эквивалентную формальную грамматику:

Если задан НКА = <Q,A,q0,d,F >,то G = <T,N,S,P> определяется следующим образом: T = A; N = Q; S=q0; P = {qi ® akqj | , если d(qi,ak) = qjÎd}È{qi ® e | , если qi Î F}.

6. Алгоритм построения НКА по заданной модифицированной грамматике:

Если задана грамматика G = <T,N,S,P>,то НКА =<Q,A,q0,d,F> определяется следующим образом: Q = N;A = T;q0 = S;d ={d(B,a)=C | B ® aCÎP};

F={qj | qj ® e Î P}.

7. Алгоритм построения детерминированного автомата по НКА. Если задан НКА = <>, то КА =

= <> определяется следующим образом :  функция d для КА определяется следующим образом: рассмотрим элемент множества ,который теперь является состоянием автомата КА и значение функции для этого автомата будет следующим: . Множество конечных состояний нового автомата .

 

Задачи и упражнения

 

1. Доказать, что объединение, конкатенация и итерация замкнуты на множестве автоматных языков

L=L1UL2         b) L=L1°L2.      с) L = L1*

2. Постройте А-грамматику для языков

L1={(01)n(10)m½n³0, m³1},            L2={anba½n³0}.

3. Дан граф конечного автомата

Подпись:  построить КА,

детерминировать КА,

минимизировать ДКА,

построить А-грамма-тику по МКА,

определить язык.

4. НКА задан таблицей. По данному автомату по-строить детерминированный конечный автомат (ДКА), по ДКА построить минимальный конечный автомат (МКА).

5. Используя результаты из задачи

Подпись: a	b
  ®A	F,E	B
B	E	D,C
C	F	C.D
D	D	A
E	E	F
F	F	E

2 для каждого языка:

построить граф КА по

грамматике GA,

построить КА,

детерминировать КА, минимизировать ДКА.

F
 
Е
 
6. Дан граф конечного автомата

построить КА,

детерминировать КА,

минимизировать ДКА.