По праволинейной грамматике построить конечный автомат, определяющий такой же язык (см. стр. 7) и продемонстрировать его работу на каком-нибудь входном слове. Детерминировать получившийся автомат (см. стр. 6-7). По детерминированному автомату составить праволинейную грамматику, эквивалентную исходной.
I → aA | aB | aC, A → a | b, B → aB | bA | λ, C → aA | bB | bC;
2 Задание 1
По словесному описанию языка (Σ={a,b,c}) составить регулярное выражение (см. стр. 2). По этому регулярному выражению построить праволинейную грамматику, порождающую данный язык (см. стр. 4) и выписать вывод какого-нибудь четырехбуквенного слова. По получившейся грамматике составить систему регулярных уравнений и попытаться её решить.
Если в слове есть буква b, то есть и a.
Решение
В словах, где есть буква b, перед ней или после нее обязательно есть буква a. Перед, между и после букв a и b в этих словах может стоять любое количество букв алфавита (или отсутствовать). Слово из любых букв алфавита (в том числе и пустое): (a+b+c)*. Слово, где буква a стоит перед буквой b: (a+b+c)*a(a+b+c)*b(a+b+c)*. Слово, где буква b стоит перед буквой a: (a+b+c)*b(a+b+c)*a(a+b+c)*. В множество слов языка также входят слова, в который нет букв b, но есть буква a или c, выражение для таких слов (a+c)*a+(a+c)*c (примем, что пустое слово не входит в язык).
Итоговое выражение для языка имеет вид (a+c)*a+(a+c)*c+(a+b+c)*a(a+b+c)*b(a+b+c)*+(a+b+c)*b(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+с)*:
G4({a,b,c},{D,E},U,E)
E→D | λ
D→aE | a
D→cE | c
=
G’4({a,b,c},{E},U,E)
E→aE | cE | λ
Грамматика для (a+c)*a (учитывая правило E→λ):
G5({a,b,c},{E},U,E)
E→aE | cE | a
Грамматика для (a+c)*c (учитывая правило E→λ):
G6({a,b,c},{E},U,E)
E→aE | cE | c
Грамматика для (a+c)*a+(a+c)*c:
G5({a,b,c},{D},{D→aD | cD | a},D)∪G6({a,b,c},{E},{E→aE | cE | c},E) =
G7({a,b,c},{D,E,F},U,F)
F→D | E
D→aD | cD | a
E→aE | cE | c
=
G’7({a,b,c},{F},U,F)
F→ aF | cF | a | c
Грамматика для итерации (a+b+с)*:
G8({a,b,c},{D,E},U,E)
E→D | λ
D→aE | a
D→bE | b
D→cE | c
=
G’8({a,b,c},{E},U,E)
E→aE | bE | cE | λ
Грамматика для (a+b+с)*a (учитывая правило E→λ):
G9({a,b,c},{E},U,E)
E→aE | bE | cE | a
Грамматика для (a+b+с)*b (учитывая правило E→λ):
G10({a,b,c},{E},U,E)
E→aE | bE | cE | b
Грамматика для (a+b+с)*b(a+b+с)*:
G10({a,b,c},{D},{D→aD | bD | cD | b},D) ∪
G’8({a,b,c},{E},{E→aE | bE | cE | λ},E) =
G11({a,b,c},{D,E},U,D)
D→aD | bD | cD | bE
E→aE | bE | cE | λ
Грамматика для (a+b+c)*a(a+b+c)*b(a+b+c)*:
G9({a,b,c},{F},{F→aF | bF | cF | a},F) ∪
G11({a,b,c},{D,E},{D→aD | bD | cD | bE; E→aE | bE | cE | λ },D) =
G12({a,b,c},{D,E,F},U,F)
F→aF | bF | cF | aD
D→aD | bD | cD | bE
E→aE | bE | cE | λ
Грамматика для a(a+b+с)*:
G13({a,b,c},{H,I},U,H)
H→aI
I→aI | bI | cI | λ
Грамматика для (a+b+c)*b(a+b+c)*a(a+b+c)*:
G11({a,b,c},{J,K},{J→aJ | bJ | cJ | bK; K→aK | bK | cK | λ },J) ∪
G13({a,b,c},{H,I},{H→aI; I→aI | bI | cI | λ},H) =
G14({a,b,c},{H,I,J,K},U,J)
J→aJ | bJ | cJ | bK
K→aK | bK | cK | H
H→aI
I→aI | bI | cI | λ
=
G’14({a,b,c},{I,J,K},U,J)
J→aJ | bJ | cJ | bK
K→aK | bK | cK | aI
I→aI | bI | cI | λ
Грамматика для
(a+b+c)*a(a+b+c)*b(a+b+c)*+(a+b+c)*b(a+b+c)*a(a+b+c)*:
G12({a,b,c},{D,E,F},
{F→aF | bF | cF | aD; D→aD | bD | cD | bE; E→aE | bE | cE | λ },F) ∪
G’14({a,b,c},{I,J,K},
{J→aJ | bJ | cJ | bK; K→aK | bK | cK | aI; I→aI | bI | cI | λ},J) =
G15({a,b,c},{D,E,F,I,J,K,L},U,L)
L→F | J
F→aF | bF | cF | aD
D→aD | bD | cD | bE
E→aE | bE | cE | λ
J→aJ | bJ | cJ | bK
K→aK | bK | cK | aI
I→aI | bI | cI | λ
=
G’15({a,b,c},{D,E,I,K,L},U,L)
L→aL | bL | cL | aD | bK
D→aD | bD | cD | bE
E→aE | bE | cE | λ
K→aK | bK | cK | aI
I→aI | bI | cI | λ
Грамматика для
(a+c)*a+(a+c)*c+(a+b+c)*a(a+b+c)*b(a+b+c)*+(a+b+c)*b(a+b+c)*a(a+b+c)*:
G’7({a,b,c},{M},{M→ aM | cM | a | c},M) ∪
G’15({a,b,c},{D,E,I,K,L},{L→aL | bL | cL | aD | bK; D→aD | bD | cD | bE; E→aE | bE | cE | λ; K→aK | bK | cK | aI; I→aI | bI | cI | λ},L) =
G16({a,b,c},{D,E,I,K,L,M,N},U,N)
N→M | L
M→ aM | cM | a | c
L→aL | bL | cL | aD | bK
D→aD | bD | cD | bE
E→aE | bE | cE | λ
K→aK | bK | cK | aI
I→aI | bI | cI | λ
Вывод слова «cbcac»
N→L→cL→cbK→cbcK→cbcaI→cbcacI→cbcac
Система регулярный уравнений:
N = M+L
M = aM+cM+a+c
L = aL+bL+cL+aD+bK
D = aD+bD+cD+bE
E = aE+bE+cE+λ
K = aK+bK+cK+aI
I = aI+bI+cI+λ
I = aI+bI+cI+λ = (a+b+c)I+λ; I = (a+b+c)*λ = (a+b+c)*
K = aK+bK+cK+aI = (a+b+c)K+a(a+b+c)*; K = (a+b+c)*a(a+b+c)*
E = aE+bE+cE+λ = (a+b+c)E+λ; E = (a+b+c)*λ = (a+b+c)*
D = aD+bD+cD+bE = (a+b+c)D+b(a+b+c)*; D = (a+b+c)*b(a+b+c)*
L = aL+bL+cL+aD+bK =
= (a+b+c)L+a(a+b+c)*b(a+b+c)*+b(a+b+c)*a(a+b+c)*;
L = (a+b+c)*(a(a+b+c)*b(a+b+c)*+b(a+b+c)*a(a+b+c)*) =
= (a+b+c)*a(a+b+c)*b(a+b+c)*+(a+b+c)*b(a+b+c)*a(a+b+c)*
M = aM+cM+a+c = (a+c)M+a+c; M = (a+c)*(a+c) = (a+c)*a+(a+c)*c
N = M+L =
= (a+c)*a+(a+c)*c+(a+b+c)*a(a+b+c)*b(a+b+c)*+(a+b+c)*b(a+b+c)*a(a+b+c)*
3 Задание 2
Задать вопрос
на новый заказ в Автор24.
