По праволинейной грамматике построить конечный автомат, определяющий такой же язык (см. стр. 7) и продемонстрировать его работу на каком-нибудь входном слове. Детерминировать получившийся автомат (см. стр. 6-7). По детерминированному автомату составить праволинейную грамматику, эквивалентную исходной.
I → aB | bB | bA, A → aI | bA | λ, B → aB | bC, C → aB;
2 Задание 1
По словесному описанию языка (Σ={a,b,c}) составить регулярное выражение (см. стр. 2). По этому регулярному выражению построить праволинейную грамматику, порождающую данный язык (см. стр. 4) и выписать вывод какого-нибудь четырехбуквенного слова. По получившейся грамматике составить систему регулярных уравнений и попытаться её решить.
На всех нечетных местах каждого слова находится a.
Решение
Во всех словах на нечетных местах стоит буква a, а на четных – a, b или c. Слова могут быть нечетной или четной длины, плюс пустое слово, так как оно четной длины. Выражение для слов нечетной длины a((a+b+c)a)*. Выражение для слов четной длины a(a+b+c)(a(a+b+c))*. Выражение для данного языка имеет вид a((a+b+c)a)*+a(a+b+c)(a(a+b+c))*+λ =
= a((a+b+c)a)*+(a(a+b+c))*.
Грамматики для a, b и c:
G1({a,b,c},{A},Q,A), G2({a,b,c},{B},R,B), G3({a,b,c},{C},T,C),
A→aB→bC→c
Грамматика для a+b+c:
G4({a,b,c},{A,B,C,D},U,D)
D→A | B | C
A→a
B→b
C→c
=
G’4({a,b,c},{D},U,D)
D→a | b | c
Грамматика для (a+b+c)a:
G5({a,b,c},{A,D},U,D)
D→ aA | bA | cA
A→a
Грамматика для итерации ((a+b+c)a)*:
G6({a,b,c},{A,D,E},U,E)
E→D | λ
D→aA | bA | cA
A→aE | a
=
G6’({a,b,c},{A,E},U,E)
E→ aA | bA | cA | λ
A→aE | a
Грамматика для a((a+b+c)a)*:
G7({a,b,c},{A,E,D},U,D)
D→aE
E→ aA | bA | cA | λ
A→aE | a
Грамматика для a(a+b+c):
G8({a,b,c},{A,D},U,A)
A→aD
D→a | b | c
Грамматика для итерации (a(a+b+c))*:
G9({a,b,c},{A,D,E},U,E)
E→A | λ
A→aD
D→aE | bE | cE | a | b | c
=
G9’({a,b,c},{D,E},U,E)
E→ aD | λ
D→aE | bE | cE | a | b | c
Грамматика для a((a+b+c)a)*+(a(a+b+c))*:
G7({a,b,c},{A,E,D},{D→aE; E→ aA | bA | cA | λ; A→aE | a},D) ∪
G9’({a,b,c},{H,I},{H→aI | λ; I→aH | bH | cH | a | b | c},H) =
G10({a,b,c},{S,A,E,D,H,I},U,S)
S→D | H
D→aE
E→ aA | bA | cA | λ
A→aE | a
H→aI | λ
I→aH | bH | cH | a | b | c
Вывод слова «abaca»
S→aE→abA→abaE→abacA→abaca
Система регулярных уравнений:
S = D+H
D = aE
E = aA+bA+cA+λ
A = aE+a
H = aI+λ
I = aH+bH+cH+a+b+c
I = aH+bH+cH+a+b+c = (a+b+c)H+(a+b+c) = (a+b+c)(aI+λ)+(a+b+c) =
= (a+b+c)aI+(a+b+c)+(a+b+c) = (a+b+c)aI+(a+b+c);
I = ((a+b+c)a)*(a+b+c)
H = aI+λ = a((a+b+c)a)*(a+b+c)+λ = ( (FG)*=λ+F(GF)*G ) (a(a+b+c))*
E = aA+bA+cA+λ = (a+b+c)A+λ
A = aE+a = a((a+b+c)A+λ)+a = a(a+b+c)A+a+a = a(a+b+c)A+a;
A = (a(a+b+c))*a =
= ( (FG)*=λ+F(GF)*G ) (λ+a((a+b+c)a)*(a+b+c))a = a+a((a+b+c)a)*(a+b+c)a
E = (a+b+c)A+λ = (a+b+c)(a+a((a+b+c)a)*(a+b+c)a)+λ =
= (a+b+c)a+(a+b+c)a((a+b+c)a)*(a+b+c)a+λ =
= (a+b+c)a((a+b+c)a)*(a+b+c)a+(a+b+c)a+λ =
= ((a+b+c)a((a+b+c)a)*+λ)(a+b+c)a+λ =
= ((a+b+c)a)*(a+b+c)a+λ =
= ( F*F=FF* ) (a+b+c)a((a+b+c)a)*+λ = ((a+b+c)a)*
D = aE = a((a+b+c)a)*
S = D+H = a((a+b+c)a)*+(a(a+b+c))*
3 Задание 2
Заказать работу
на новый заказ в Автор24.
