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

i think then also it will be false as best answer says there are chances that we dont have transition on each alphabet

---

Hint
For statement II

Take A as a finite regular language. Then for any (regular / non-regular) language B:

                                             $A \cap B \subseteq A$


Since A is finite,  $A \cap B $ is also finite.

---

@Reetu Chaudhary if in 1st stmt : DFA instead of NFA, then statement become true, 

i know best answer say's that chances that we don't have transition on each alphabet -> but it's only valid for NFA, for DFA we must have transition on all alphabets. 

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

EXPLAINATION FOR STATEMENT 1 BEING FALSE.

Yes, the core reason the NFA doesn't accept all of Σ* — despite all of its states being accepting — is because of the existence of dead (non-reachable or trap) states in the corresponding DFA. Let’s go deeper into this:

Let’s revisit the NFA:

• States: {q0}

• Start state: q0

• Accepting states: q0

• Alphabet: {a, b}

• Transitions:

  • q0 --a--> q0

  • no transition on b

This NFA accepts only strings in a*, not strings like b, ab, aab, etc.

🔴 Even if all NFA states are accepting, the language ≠ Σ*
Because after determinization, some strings may land in a trap state, due to missing transitions in NFA.

credit - chatGPT

---

@Aditya 6 Yes. Incase of DFA, it'll be (sigma)*

---

@Franz Kafka can we take A as empty language.
 

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.

Answer 4

Answer is option B . You can refer to any of the answers above .

This comment is added just to emphasize the importance of quantifier.

In option B we have THERE EXIST a regular language A such that for all languages B, A intersection B is regular.

This becomes True as let A={} and B =a^nb^n

So ther intersection is {} which is regular

Now suppose option goes like FOR ALL regular language A ,A intersection B is regular.

This would have been False

Ex- let A=(a+b)* and B =a^nb^n

Then A intersection B is a^nb^b which is DCFL but not regular

Comments

Yeah! I first thought that we are considering all regular languages and i ignored "There Exists".

Answer 5

Correcr Answer :: B

Statement 1 = If all states of DFA are accepting states then we can say that langusge accepted by it is (sigma*) , but we cant say this in case of NFA so statement 1 is wrong

Statement 2 = it is correct as intersection of regular language to any language is regular language

Answer 6

1) I think that in NFA transitions to other states may or may not be present. Let's say we have to States A and B which are connected by only "a".Taking Sigma={a,b}.THUS "b" can never be accepted by this NFA.

HENCE {a,b}★ also can't be accepted.

 

2) INTERSECTION WITH REGULAR LANGUAGE IS ALWAYS REGULAR

Comments

Believe me, this was what I initially thought for 1.