Search code examples
grammarcontext-free-grammarautomataturing-machinesautomata-theory

Some NFA & REGULAR LANGUAGE & Equivalences

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):

enter image description here

Solution

  • 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*.