Find, if possible, a finite automaton that recognizes $L(G) = 0^*(1022^* + 2(00)^*)$

92 Views Asked by At

(Related: Find language generated by a grammar).

Given the grammar $G=(\{S,A,B\},\{0,1,2\},P,S)$ where $$P\colon S\to0S\mid10A\mid2B,\;A\to2A+2,\;B\to00B+\lambda,$$ find, if applicable, a finite automaton that recognizes the language that it generates. If not, justify.

First of fall in the given link we showed that altough is a context-free grammar, it is in fact a regular language: $L(G) = 0^*(1022^* + 2(00)^*)$. So I draw this finite automaton:

Finite automaton

Is my automaton correct?

1

There are 1 best solutions below

0
On BEST ANSWER

(Upgrading my comment into an answer, just to have an answer for this):

This certainly looks correct to me! One small bit of nitpickery, though: depending on your specific definition of a Deterministic Finite Automaton, you may want to add all of the 'missing' transitions as explicit transitions to a common failure state; the standard definition requires a transition from each state for each symbol, which this doesn't show.

Also, as a secondary followup: note that you could determine this diagram by building the diagrams for $A$ and $B$ as 'subautomata' of a sort; can you see which nodes correspond specifically to the 'start states' for each of those?

(Also also, you could note that the grammar itself is regular and not just context-free: per the definitions at https://en.wikipedia.org/wiki/Regular_grammar it's an extended right-regular grammar.)