What is the Regular Expression for

Question

The regular expression for the language recognized by the following Finite State Automaton is?

• A. $0^* \mid 0^* 1^+$
• B. $0^* \mid 11^*$
• C. $0^* \mid 0^* 1^+ \mid 0^* 1^+ (0+1)^*$
• D. None of these.

Answer 1

Using Arden's Theorem 

A= ∈ + A0  - - - - I 

B = A1 + B1--------II 

C = B0+ C0+ C1 -- - - III  

Apply Arden's Theorem in I

​A= ∈0* = 0*    - - - IV

​Put IV in II

​B = 0*1 + B1

apply arden's theorem 

​B = 0*11* =0*1⁺  - - - -  V

both A and B are final states 

​Regular expression = A + B 

= 0* +0*1⁺ 

Option a. 

[ Note:Arden's Theorem : if R = Q+RP then R=QP*

No need to find C as it is dead state]  

Comments

sir why not option C , it is also satisfying ...0* | 11* ..by this we can also reach both the final States..

---

1. Regular expression = sum of equation of final states always, so A+B

2.Secondly We can find C by Putting value of B in equation III and applying arden's theorem. But what is use (even if calculated) as regular expression is A+B (final states only)

3.It is clear C is not a final state and dead state, once we reach there we cannot go anywhere (no out going arrow or no transition to reach any other state or from start to final we never go through C), so no need to look at C.

---

not containg   1   0  as substring

Answer 2

answer = option A

option B fails as it accepts extra strings than those in the Language represented by the DFA.
option C fails as it fails to accept the form $0^*1^+$

option A successfully represents the language accepted by the DFA, also it rejects strings which are not in the language.