edited by
8,668 views
33 votes
33 votes

The regular expression for the language recognized by the finite state automaton of figure is ________

edited by

5 Answers

Best answer
59 votes
59 votes
Using Arden's theorem to find the regular expression :

$A = \epsilon + A0 = \epsilon0^* = 0^*$

$B = A1 + B1 = 0^*1 +B1 = 0^*11^* $

As there are two final states, we should union both RE.

$\implies 0^∗+0^∗11^∗=0^∗(\epsilon +11^∗)=0^∗(\epsilon+1^+)=0^∗1^∗%=0^∗+0^∗11^∗=0^∗(\epsilon+11^∗)=0^∗(\epsilon+1^+)=0^∗1^∗ $

Note that $\epsilon+1^+=1^∗$

PS : Ardens theorem -  Let $P$ and $Q$ be two regular expressions. If $P$ does not contain null string, then $R = Q + RP$ has a unique solution which is $R = QP^*$

$L=0^*1^*$
$L$ contains all binary strings where any $1$ is not followed by any $0$.
edited by
0 votes
0 votes

Clearly , looking into DFA we can say that C is Dead state.

Using Arden's theoram to find the regular expression :

A = ε + A0ε0* = 0*

B = A1 + B1 = 0*1 +B1 = 0*11* = 0*1*

Therefore answer is 0*1*

PS : Ardens theoram - 

Let P and Q be two regular expressions.

If P does not contain null string, then R = Q + RP has a unique solution that is R = QP*

0 votes
0 votes

Things worth noting in this question are:

  • As you can see in the figure, any number of ‘0s’ are allowed at state A and then if a ‘1’ arrives we move to state B. Then any number of ‘1s’ are allowed. 
  • also if after getting a ‘1’ we get another ‘0’ then we fall in dead state at C. This means no number of ‘0s’ is allowed after getting a ‘1’.
  • No ‘1’ is followed by any ‘0’

Therefore language accepted by this DFA is: 

                                           0*1*

Related questions

21 votes
21 votes
2 answers
1
Kathleen asked Oct 4, 2014
3,593 views
Consider $n$-bit (including sign bit) $2's$ complement representation of integer numbers. The range of integer values, $N$, that can be represented is ______ $\leq N \leq...
19 votes
19 votes
3 answers
2
Kathleen asked Oct 4, 2014
7,979 views
The number of edges in a regular graph of degree $d$ and $n$ vertices is ____________
31 votes
31 votes
4 answers
3
Kathleen asked Oct 4, 2014
5,517 views
The number of subsets $\left\{ 1,2, \dots, n\right\}$ with odd cardinality is ___________
17 votes
17 votes
4 answers
4
Kathleen asked Oct 4, 2014
4,382 views
The Hasse diagrams of all the lattices with up to four elements are ________ (write all the relevant Hasse diagrams)