it's wrong question. The statement will be

" Either L can be {a^{n} | n is odd} or L can be {a^{n} | n is even}"

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+24 votes

What can be said about a regular language $L$ over $\{ a \}$ whose minimal finite state automaton has two states?

- $L$ must be $\{a^n \mid n \ \text{ is odd}\}$
- $L$ must be $\{a^n \mid n \ \text{ is even}\}$
- $L$ must be $\{a^n \mid n \geq 0\}$
- Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$

+24 votes

Best answer

0 votes

option A require two states in MFA

option B require two states in MFA

option C require one states in MFA

option D is union of option A and B so if we find DFA for union we get two states then it further minimized to only one state ( both state will be final state in union)

**Answer is ****A,B**

correct me if wrong :)

+1

There is no grammatical error. (They mean it must be L1 but not L2...... OR it must be L2 but not L1)

But by option D they want to say either option A or B.... so answer is D.

but why there will be the union of two languages?

I) Either L must be {a^{n }| n is odd}, or L must be {a^{n }| n is even}

II) L must be {a^{n }| n is odd || n is even}

I and II are not same.

0 votes

Ans 4) Either L must be {a^{n }| n is odd}, or L must be {a^{n }| n is even}

option A) Wrong because even case can also be true.

option B) Wrong because odd case can also be true.

option C) A regular language L over {a} with 2 states can have both final states and hence this can also be true. BUT in the question it is mentioned **"whose minimal finite state automaton has two states". So if we want to accept all strings the minimal finite state automaton, it will contain 1 state (minimum). Since in the question it is mentioned 2 states in minimal finite automata hence (D) is the correct option.**

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 5k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.4k
- Admissions 412
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,942 questions

41,952 answers

119,194 comments

41,471 users