We can reduce given automata to this-

The Gateway to Computer Science Excellence

+29 votes

Best answer

+10 votes

given DFA accept a but option A and D cant so A and D are eliminated

option B accept epsilon but given DFA cant accept epsilon so B eliminated

**Hence Ans is C**

q3 i unreachabl state wo we remove it now both q1 and q2 are equivalent so they can combine now we easily find regular expression for it : b*a(a+b)*

+5 votes

I will proceed with elimination of options

Option A: wrong because, string "ba" is accepted by given DFA. R.E given here can't generate it.

Option B: epsilon can't be accepted by given DFA. Given R.E generates epsilon

Option D: Same reason as option A. As "ba" can't be generated here too. The least it can generate are aa,baa,bbaa... so on..

Option C is correct. How???

After reaching q1, the DFA can accept any string generated by the alphabet{a,b}. b* is obvious from the given figure. to reach q1 we need atleast one a. Hence, b*a(a+b)^* is correct R.E

Option A: wrong because, string "ba" is accepted by given DFA. R.E given here can't generate it.

Option B: epsilon can't be accepted by given DFA. Given R.E generates epsilon

Option D: Same reason as option A. As "ba" can't be generated here too. The least it can generate are aa,baa,bbaa... so on..

Option C is correct. How???

After reaching q1, the DFA can accept any string generated by the alphabet{a,b}. b* is obvious from the given figure. to reach q1 we need atleast one a. Hence, b*a(a+b)^* is correct R.E

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,523 answers

195,607 comments

101,286 users