The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
1.2k views

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

  1. $L$ must be $\{a^n \mid n \  \text{ is odd}\}$
  2. $L$ must be $\{a^n \mid n \  \text{ is even}\}$
  3. $L$ must be $\{a^n \mid n \geq 0\}$
  4. Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$

 

 

asked in Theory of Computation by Veteran (59.4k points)
edited by | 1.2k views
+3

it's wrong question. The statement will be 

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

0
"must be" needs to be replaced with "can be" because the language with two states in minimal dfa can be some something else too like a^+.

6 Answers

+24 votes
Best answer

Ans (D) Either $L$ must be  $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$

Because if we draw the minimal dfa for each of them, we will get two states each.
Whereas, $\{a^n \mid n \geq 0\}$ requires only one state.

answered by Loyal (6.1k points)
edited by
–1

Is it not a wrong question?

Explanation- Option D) states that- L "must be"  {a| n is odd}, or L must be {a| n is even}

But, L can also be- 

L={a| n>0 } 

or

L={epsilon}

Both the Languages also need two states in the minimum DFA.

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 :)

answered by Active (2.2k points)
+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 is odd}, or L must be {a| n is even}
II) L must be  {a| n is odd || n is even}

I and II are not same.

0
ok that i got now , but option A and B also have only 2 states in MFA
+1
> You are going to pick only one option. So D is the ans.
> The keyword "must" clearly makes option A & B false.
0

What if n = 0 then {a| n is even} boils down to {a0} = {Epsilon}. But Two state is not required to accept Epsilon. Where am I wrong ?

0 votes

Ans 4) Either L must be  {a| n is odd}, or L must be {a| 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.
 

answered by (53 points)
0 votes
answer is D
answered by (189 points)
–1 vote

Ans: D Either L must be  {a| n is odd}, or L must be {a| n is even}

 

answered by Loyal (7k points)
–1 vote

Correct answer is (D) only.
a. DFA needs two states, make second state final.
b. DFA needs two states, make first state final.
c. DFA needs one state, make that state final.
d. DFA needs two states, make both the states final.

answered by Boss (39k points)
edited by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,942 questions
41,952 answers
119,194 comments
41,471 users