10_UAZS_dla_GBK.pdf

(237 KB) Pobierz
Konstrukcja UAZS dla danej gramatyki bezkontekstowej.
I.
Dana jest gramatyka bezkontekstowa:
= == =
G
(((( ))))
,
N
,
S
,
P
II. Konstruujemy gramatykħ
G
====
( (( ( ) )) )
N
,
S
,
P
rwnowaŇnĢ G, takĢ Ňe
NN a : ,
P powstaje z P wedþug zasady:
C
a
= == =
{{{{}}}}
a) w kaŇdej regule
(((( ))))
A
P
wszystkie
a
a
zastħpujemy przez
C ,
b) dodajemy reguþy postaci
C a a
a
III. Konstruujemy UAZS ,
M
==== , taki Ňe
( (( ( ) )) )
,
,
Q
,
q
,
,
F
0
L
( (( () )) )( (( () )) )
M
==== :
L
G
= == =N
{{{{}}}}
#
= == = ,
q f .
Q
{{{{}}}}
q
N
f
q = == =
S
0
F ====
{{{{}}}}
q
f
Funkcja przejĻcia dana jest przez instrukcje:
dla
(((( ))))
A
a 1
A
K
A
n
P
A
,
,
a
A
1 ,
A
n K
A
n
1
2
dla
(((( ))))
A
P
A
,
a
,
x
x
,
a
a
A
,
a
,
#
q
,
#
a
f
dla
( (( ( ) )) )
A
P
A
,
,
x
x
,
a
a
A
,
,
#
q
,
#
.
a
f
Zadanie przykþadowe: GBK UAZS
Przeksztaþę gramatykħ bezkontekstowĢ G na uoglniony
automat ze stosem (UAZS) akceptujĢcy jħzyk
L .
(((())))
G:
S
aaSb
|
bAa
WyprowadŅ w gramatyce G sþowo aabaabbab oraz znajdŅ dla
tego sþowa obliczenie akceptujĢce w automacie ze stosem.
A
aAbb
|
a
RozwiĢzanie:
I.
G
==== ,
( (( ( ) )) )
,
N
,
S
,
P
{ {{ {} }} }
a,
b
,
N
====
{ {{ {} }} }
S
,
A
====
Wyprowadzenie sþowa aabaabbab w gramatyce G:
S
aaSb
aabAab
aabaAbbab
aabaabbab
II.
G
====
( (( ( ) )) )
,
N
,
S
,
P
,
N
====
{{{{ }}}}
S
,
A
,
C
a C
,
,
b
Reguþy produkcji
P
:
S
C
C
SC
|
C
AC
a
a
b
b
a
A
C
AC
C
|
a
a
b
b
C a
a
C b
b
III. UAZS ,
M
==== ,
(((( ))))
,
,
Q
,
q
,
,
F
0
====
N ====
{{{{}}}} {{{{ }}}}
#
S
,
A
,
C
a C
,
,
#
b
Q
=
N
{}{ }
q
=
S
,
A
,
C
,
C
,
q
,
q f
.
N
f
a
b
f
q = == =
S
0
F ====
{{{{}}}}
q
f
Funkcja przejĻcia :
Reguþa
Instrukcja
1)
S
C
C
SC
1)
S
,,
C
,
C
SC
a
a
b
a
b
a
2)
S
C
b AC
2)
S
,,
C
b ,
C
A
a
a
3)
3)
A
C
AC
C
A
,,
C
a ,
C
C
A
a
b
b
b
b
4)
A
4a)
aA
a
,
,
x
x
,
4b)
aA
,
,
#
q
,
#
f
5)
C a
a
5a)
C a
,
a
,
x
x
,
5b)
C
,
,
#
q
,
#
a
f
6)
C b
b
6a)
C b
,
b
,
x
x
,
6b)
C
,
,
#
q
,
#
b
f
Dla sþowa aabaabbab
Wyprowadzenie w G Obliczenie akceptujĢce w M
S
[[[[
S
,aabaabbab
,
#
]]]]
C
C
SC
| 1 − −− −
[[[[
C
,
aabaabbab
,
#
C
SC
]]]]
1
a
a
b
a
b
a
aC
a SC
|
[[[[
C
,
abaabbab
,
#
C
S
]]]]
− −− −
5
b
5
a
a
b
aaSC
|
− −− −
[[[[
S
,
baabbab
,
#
C
]]]]
5
b
5
a
b
aaC
AC
C
|
[[[[
C
,
baabbab
,
#
C
C
A
]]]
− −− −
2
b
a
b
2
b
b
a
aabAC
a C
|
− −− −
[[[[
A
,
aabbab
,
#
C
C
]]]]
6
b
6
a
b
a
aabC
AC
C
C
C
|
[[[[
C
,
aabbab
,
#
C
C
C
C
A
]]]
− −− −
3
a
b
b
a
b
3
a
b
a
b
b
aabaAC
C
C
C
|
−−−−
[[[[
A
,
abbab
,
#
C
C
C
C
]]]]
5
b
b
a
b
5
a
b
a
b
b
aabaaC
C
C
C
|
− −− −
[[[[
C
,
bbab
,
#
C
C
C
]]]]
4
b
b
a
b
4
b
b
a
b
aabaabC
C
C
|
−−−−
[[[[
C
,
bab
,
#
C
C
]]]]
6
b
a
b
6
a
b
b
a
aabaabbC
a C
|
−−−−
[[[[
C
,
ab
,
#
C
]]]]
6
b
6
a
a
b
aabaabbaC
|
− −− −
[[[[
C b
,
b
,
#
]]]]
5
b
5
a
aabaabbab
|
− −− −
b q
[[[[ ]]]]
,
,
#
6
6
f
.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin