Ülesanne 6.
Keel ei ole regulaarne, sest talle ei ole võimalik koostada sellist regulaarset grammatikat, mis tagaks, et nullide arv pärast ühtesid oleks võrdne nullide arvuga enne ühtesid.
Grammatika
G:{
S
-
>aA
S->bA
A->aB
A->bB
B->aS
B->bS
S->
e
}
Regulaarne avaldis:
((a+b)
3
)
*
Automaat
Grammatika
G:{
S->0S
S->1A
S->0
S->1
S->e
A->1A
A->0B
A->1
A->0
B->0S
B->0
}
Regulaarne avaldis
(0
*
1
+
0
2
)
*
+0
*
1(1
*
00
+
1)
*
+0
*
1
+
0(0
+
1
+
0)
*
Automaat