По праволинейной грамматике построить конечный автомат, определяющий такой же язык (см. стр. 7) и продемонстрировать его работу на каком-нибудь входном слове. Детерминировать получившийся автомат (см. стр. 6-7). По детерминированному автомату составить праволинейную грамматику, эквивалентную исходной.
I → aI | bA | bC, A → bI | bB | b, B → a | bA | b, C → aA | b;
2 Задание 1
По словесному описанию языка (Σ={a,b,c}) составить регулярное выражение (см. стр. 2). По этому регулярному выражению построить праволинейную грамматику, порождающую данный язык (см. стр. 4) и выписать вывод какого-нибудь четырехбуквенного слова. По получившейся грамматике составить систему регулярных уравнений и попытаться её решить.
Каждое слово содержит не менее 3-х букв a.
Решение
В словах языка обязательно присутствуют три буквы a. До, между ними и после могут быть любые слова из букв a,b и c. Выражение для таких слов (a+b+c)*. Cлова языка - конкатенация множеств (a+b+c)* с буквами a между ними. Выражение для данного языка имеет вид (a+b+с)*a(a+b+c)*a(a+b+c)*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,D},U,D)
D→A
D→B
D→C
A→a
B→b
B→c
=
G’4({a,b,c},{D},U,D)
D→a
D→b
D→c
Грамматика для (a+b+c)*:
G5({a,b,c},{D,E},U,E)
E→D | λ
D→aE | a
D→bE | b
D→cE | c
=
G’5({a,b,c},{E},U,E)
E→aE | bE | cE | a | b | c | λ
Грамматика для (a+b+c)*a (учитывая правило E→λ):
G6({a,b,c},{A,E},U,E)
A→a
E→aE | bE | cE | aA | bA | cA
E→a
=
E→aE | bE | cE | aA | bA | cA | a
A→a
Грамматика для (a+b+c)*a(a+b+c)*a:
G6({a,b,c},{A,E},{E→aE | bE | cE | aA | bA | cA | a;A→a},E) ∪
G’6({a,b,c},{B,C},{B→aB | bB | cB | aC | bC | cC | a;C→a},B) =
G7({a,b,c},{A,B,C,E},U,E)
E→aE | bE | cE | aA | bA | cA | aB
A→aB
B→aB | bB | cB | aC | bC | cC | a
C→a
Грамматика для (a+b+c)*a(a+b+c)*a(a+b+c)*a:
G7({a,b,c},{A,B,C,E},{E→aE | bE | cE | aA | bA | cA | aB;A→aB;B→aB | bB | cB | aC | bC | cC | a; C→a },E) ∪ G6({a,b,c},{D,F},{D→aD | bD | cD | aF | bF | cF | a; F→a },D) =
G8({a,b,c},{A,B,C,D,E,F},U,E)
E→aE | bE | cE | aA | bA | cA | aB
A→aB
B→aB | bB | cB | aC | bC | cC | aD
C→aD
D→aD | bD | cD | aF | bF | cF | a
F→a
Грамматика для (a+b+c)*a(a+b+c)*a(a+b+c)*a(a+b+c)*:
G8({a,b,c},{A,B,C,D,E,F},{E→aE | bE | cE | aA | bA | cA | aB; A→aB; B→aB | bB | cB | aC | bC | cC | aD; C→aD; D→aD | bD | cD | aF | bF | cF | a;
F→a },E) ∪ G5({a,b,c},{H},{H→aH | bH | cH | a | b | c | λ},H) =
G9({a,b,c},{A,B,C,D,E,F,H},U,E)
E→aE | bE | cE | aA | bA | cA | aB
A→aB
B→aB | bB | cB | aC | bC | cC | aD
C→aD
D→aD | bD | cD | aF | bF | cF | aH
F→aH
H→aH | bH | cH | a | b | c | λ
Вывод слова «aaab»
E→aB→aaD→aaaH→aaab
Система регулярный уравнений:
E = aE+bE+cE+aA+bA+cA+aB
A = aB
B = aB+bB+cB+aC+bC+cC+aD
C = aD
D = aD+bD+cD+aF+bF+cF+aH
F = aH
H = aH+bH+cH+a+b+c+λ
H = aH+bH+cH+a+b+c+λ; H = (a+b+c)*(a+b+c+λ)
F = aH = a(a+b+c)*(a+b+c+λ)
D = aD+bD+cD+aF+bF+cF+aH = aD+bD+cD+aa(a+b+c)*(a+b+c+λ)+ba(a+b+c)*(a+b+c+λ)+ca(a+b+c)*(a+b+c+λ)+a(a+b+c)*(a+b+c+λ);
D = (a+b+c)*(aa(a+b+c)*(a+b+c+λ)+ba(a+b+c)*(a+b+c+λ)+ca(a+b+c)*(a+b+c+λ)+a(a+b+c)*(a+b+c+λ)) = (a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)
C = aD = a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)
B = aB+bB+cB+aC+bC+cC+aD = aB+bB+cB+aa(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+ba(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+ca(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ);
B = (a+b+c)*(aa(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+ba(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+ca(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)) = (a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)
A = aB = a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)
E = aE+bE+cE+aA+bA+cA+aB = aE+bE+cE+aa(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+ba(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+ca(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ);
E = (a+b+c)*(aa(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+ba(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+ca(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)+a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)) = (a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ)a(a+b+c)*(a+b+c+λ) = (a+b+c)*a(a+b+c)*a(a+b+c)*a(a+b+c)*
Задать вопрос
на новый заказ в Автор24.
