I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the language of this figures (nfa, regular expression and grammar):
They are in fact equivalent, but this is a strange way of converting one to the other.
R
is the same as (a|b)b*
. M
recognizes (a|b)(bb)*b?
. The right part recognizes 2*n+1
or 2*n
b
's, where n>=0
, hence is equivalent to R
.
Now on G
A
recognizes (bb)*b?
, which is equivalent to b*
(see comment on M
).
B
recognizes bB|bb*|e
which is equivalent to bB|b*
which is equivalent to b*
.
S
recognizes ab*b*|bb*b
which is equivalent to ab*|bbb*
, which is equivalent to (a|bb)b*
.