GATE CSE 2016 Set 2 | Question: 42

Question

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?

• A. Only I is true
• B. Only II is true
• C. Both I and II are true
• D. Both I and II are false

Comments

II There exists a regular language A such that for all languages B, A ∩ B is regular.

In II as soon as you see  “there exist” keyword, immediately we need to remember in there exist if for atleast one example the statement holds( ie true) the entire statement becomes true according to discrete math logic. 

Example: let A={ab,b} B={b} both A and B are regular. B can be any language as its mentioned for all languages in question. A ∩ B = {b} = Regular 

Concentrate on there exist key word

---

If instead of NFA there is DFA then that statement will be true.

---

No, its different.

Answer 1

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.

Comments

yes

---

So, option 2 is false.

---

No

The statement says there exists (asking for atleast one language) where A (regular) intersection B(any other language) is regular.

So its true.

Answer 2

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.
 

Answer 3

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 A so it is regular. Intersection of finite language with any language B is finite so$ A∩B$ is regular

Answer is B II only

Comments

Right. A can be an infinite language as well.Ex : A={a$^{2n}$:n>=0},B={a$^{2n+1}$:n>=0}, A$\cap$B={} => regular language.