Domino-Problem: Beispiel
M = ({z0, z1, z2, z3, z4, q}, {a, b}, {a, b, }, δ, z0, , {q})
mit Überführungsfunktion δ:
z0
z1
z2
z3
z4
a {(z0, a, R), (z1, a, R)} {(z2, a, R)}
∅
{(z3, a, R)} {(z4, , L)}
b
{(z0, b, R)}
∅
{(z3, b, R)} {(z3, b, R)} {(z4, , L)}
∅
∅
∅
{(z4, , L)} {(q, , N )}
Akzeptierender Lauf für aaab:
z0aaab ` az0aab ` aaz1ab ` aaaz2b ` aaabz3 ` aaaz4b ` aaz4a `
az4a ` z4a ` z4 ` q
B. Reichel, R. Stiebe
1
Domino-Spiel für M
a
@
@
@
#
@
#
a
#
@
@
#
z1@@
b
@
@
# @z4
z4b@@
z a
# z3
a @@
@ 3
@
@
@
#
b
@
@
#
@
@
2@
z
#
z2a@
z
@
b
@
@
#
z b
B. Reichel, R. Stiebe
z
#
z 2@
@
2 @@
@
@
# @z4
z4@@
z b
# z3
b @@
@
z0a
#@@z0
a @@
@ 3
@
@
a
#
@
@
@
@
@
z0 @ #
z0@a@
@
2@
@
2 @@
@
@
@
@
@
@
@
@
@
a
@
@
@
@
@
@
1@
z
b
@
@
z z #
@
@3
4@
@
@
@
z4a
z4 @ #
@
@@
@
@
@
@
b
z0 @ #
@
z0b@@
@
@
z
a
#
z a
3@
@
3 @
@
z0a
#@@z1
a @@
@
@
z0 @ #
@
z0@@
@
@
z
b
#
z b
3@
@
3 @@
z0b
#@@z0
b @@
@
@
@
@
z4b
z4 @ #
@
@@
@
@4
@
@
@
@
@
a
z1 @ #
z1@a@
@
@
@
z
#
z3@@
3@
@
z1a
#@@z2
a @@
@
@
@ b
z1 @ #
@
z1b@@
@
a
@
@
# z4
z4a@
@
@
@
z2b
#@@z3
b @@
@
@
z # @#
q @@
2
Rahmen für Eingabe aaab
z0 a
a
a
b
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
q
B. Reichel, R. Stiebe
3
Akzeptierender Lauf und Domino-Lösung
z0 a
a
a
b
z0 a @ a @ a @ b @ @@
@
# @# # @z0 z0@@# #@@# #@@# #@@#
@@ a @@ z0 a@@ a @@ b @@ @@
@ @ a
@ z0 a @ a
@ b
@ @
@
@ z z@
@
# @# # @# # @ 1 1 @# # @# #@@#
@@ a @@ a @@ z1 a@@ b @@ @@
@ z1 a @ b
@ @ @ a
@ a
@
@
@
@ z z@
# @# # @# # @# # @ 2 2 @# #@@#
@@ a @@ a @@ a @@ z2 b@@ @@
@z b @ @ @ a
@ a
@ a
2
@
@
@
@
# @# # @# # @# # @# #@@z3 z3@@#
@@ a @@ a @@ a @@ b @@ z3 @@
@ b
@z @ @ a
@ a
@ a
@
@
@
@
@ z z @3
# @# # @# # @# # @# # @ 4 4 @#
@@ a @@ a @@ a @@ z4 b@@ @@
@ @ a
@ a
@ a
@z b @ @
@
@
@ z z @4
# @# # @# # @# # @ 4 4 @# #@@#
@@ a @@ a @@ z4 a@@ @@ @@
@ @ a
@ a
@ z4 a @ @ @
@
@ z z@
@
# @# # @# # @ 4 4 @# # @# #@@#
@@ a @@ z4 a@@ @@ @@ @@
@ @ a
@ z4 a @ @ @ @
@ z z@
@
@
# @# # @ 4 4 @# # @# # @# #@@#
@@ z4 a@@ @@ @@ @@ @@
@ @ z4 a @ @ @ @ @ z z@
@
@
@
# @ 4 4 @# # @# # @# # @# #@@#
z4 @@ @@ @@ @@ @@ @@
@z @ @ @ @ @ @4
@
@
@
@
# @# # @# # @# # @# # @# #@@#
q @@ @@ @@ @@ @@ @@
@
#
#
#
#
#
#
#
#
#
#
q
B. Reichel, R. Stiebe
#
#
#
#
#
#
#
#
#
#
4
© Copyright 2024 ExpyDoc
