edited by
24,909 views
79 votes
79 votes

Consider the following two statements:

  1. If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$.
  2. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular.

Which one of the following is CORRECT?

  1. Onlyis true
  2. Only II is true
  3. Bothand II are true
  4. Both I and II are false
edited by

3 Answers

Best answer
149 votes
149 votes
  1. False, as in NFA, it is not necessary that all states have transitions for all symbols. 
  2. True, there exists a regular language $A=\{\}$, such that for all languages $B$, $A\cap B =\{\}$ is regular 

So, answer is option B.

edited by
3 votes
3 votes

Its False, suppose language is finite for example L = { $\epsilon$ , a , aa, aab, aabb } over alphabet {a,b}
Its NFA will look something like this.

Even though all states are final state in NFA, there are many string which is present in ∑* , but NFA is not capable of accepting it.
 

0 votes
0 votes
  1. all transitions may not be defined in an NFA so even if all states are final then also NFA may not accept $Σ^∗$-------------false
  2. take any finite language so it is regular. Intersection of finite language with any language B is finite so$ A∩B$ is regular

Answer is B II only

Answer:

Related questions

38 votes
38 votes
5 answers
1
Akash Kanase asked Feb 12, 2016
15,610 views
The number of states in the minimum sized DFA that accepts the language defined by the regular expression.$(0+1)^{*} (0+1) (0+1)^{*}$is ________.