What is the language generated by G and how to draw the finite state automaton that recognizes this language?

284 Views Asked by At
G = (V, T, S, P)
V = (0, 1, A, B, S) 
T = {0, 1}
S is start

S -> 0A
S -> 1A
A -> 0B
B -> 1A
B -> 1 

For the drawing, I am confused about the last part where if B is 1, it can go back to A, or it can just return 1. How do I show this?

My attempt: enter image description here

2

There are 2 best solutions below

0
On BEST ANSWER

First, be careful about your loops at $A$ and $B$ with symbols $1$ and $0$ respectively: if a symbol can't occur in a string in your language at a certain point, the arrow corresponding to that symbol should go to a "dead-end" nonaccepting state or it shouldn't be drawn at all (depending on your convention).

Second: you won't be able to build a DFA with only the states $S, A, B$. Notice that the words in the language start with $0$ or $1$, then have a $0$ and alternate between $0$ and $1$ for a while, finally ending with $1$. This means that your language is $(0+1)01(01)^*$.

We can achieve this with 5 states ($S$, $A_0$, $A$, $B$, $F$) where $A$ is the only accepting state: an arrow from $S$ to $A_0$ with labels $0,1$, an arrow from $A_0$ to $B$ with label $0$, from $B$ to $A$ with label $1$, and from $A$ to $B$ with label $0$ (and all other possible arrows go to $F$, which is our dead-end nonaccepting state, or don't exist, depending on your convention).

1
On

B should not be accepting, because it does not generate $\epsilon$ in your grammar. You should add an accepting state to your automaton, call it $F$, and $B$ can go to $F$ by reading $1$. No transition leaves $F$.

Also, why did you put a $1$-loop on state $A$ ? I don't see the rule $A\to 1A$ in your grammar. Same for the $0$-loop on $B$.

The language described by your grammar is $(0+1)0(10)^*1$.