Which of the following is/are TRUE?
A. If an NFA N<sub style="">1</sub> = { Q<sub style="">1</sub> , ∑ , δ<sub style="">1</sub> , q<sub style="">0</sub> , F<sub style="">1</sub> } and its equivalent DFA N<sub style="">2</sub> = { Q<sub style="">2</sub> , ∑ , δ<sub style="">2</sub> , q<sub style="">0</sub> , F<sub style="">2</sub> } , then Q<sub style="">2 </sub>⊆ Q<sub style="">1</sub> and F<sub style="">2 </sub>⊆ Q<sub style="">1</sub>
B. Corresponding to every NFA there is an equivalent Right linear grammar
C. L is regular iff there exist a NFA without any dead configuration which accepts L
D. If L is set of all strings ending with atleast n b’s then minimum no. of states in NFA that accept L is n+2 .
Please scroll down to see the correct answer and solution guide.
Right Answer is:
SOLUTION
Option 1: FALSE
If an NFA N1 = { Q1 , ∑ , δ1 , q0 , F1 } and its equivalent DFA N2 = { Q2 , ∑ , δ2 , q0 , F2 }, then Q2 and F2 are the subset or equal to the power set of Q1 i.e, Q2 ⊆ 2Q1 and F2 ⊆ 2Q1.
Option 2: TRUE
For every NFA these exits an equivalent
- DFA
- Regular Grammar (Right linear or Left linear Grammar)
Hence, corresponding to every NFA there is an equivalent Right linear grammar
Option 3: TRUE
This the variation of Kleene’s Theorem, it states that any regular language is accepted by an FA and conversely that any language accepted by an FA is regular.
Option 4: FALSE
If L is set of all strings ending with at least n b’s then minimum no. of states in NFA that accept L is n+1 .
Hence, False
Other variations of Kleene’s theorem
- L is regular iff there exist a NFA without any dead configuration which accepts L
- L is regular iff there exist a NFA without any choice which accepts L
- L is regular iff there exist a NFA with single final state which accepts L
- L is regular iff there exist a NFA without ε moves which accepts L