4,093 views
9 votes
9 votes
A Language is said to be regular iff

a. There exists a Right Linear Regular Grammar for L

b. There exists a Left Linear Regular Grammar for L

c. There exists a NFA with a single final state

d. There exists a DFA with a single final state

e. There exists a NFA without ԑ - move.

3 Answers

Best answer
7 votes
7 votes
A, B, C, E are TRUE. C choice.

For D consider the regular language $\{0, 00\}$. We cannot make a DFA with a single final state. But for any NFA, we can reduce it to an equivalent NFA with a single final state- just make a new final state, mark all final states as non-final and add an epsilon-transition from those final states to the new one.
selected by
1 votes
1 votes
Well the options are independent of each other that’s why. take each separately and see.

Option A) Language is regular iff it is right linear yes because you can convert a left linear to right linear .

Option B) Language is regular iff it is left linear yes because you can convert a right linear to left linear .

Option C) Language is regular iff NFA with one state yes because you can add epsilon move to make multiple final state to one single state.

Option D)Language is regular iff DFA with one single state . NO because you cannot convert a DFA with multiple Final state to single state.

Option E) Language is regular iff NFA without epsilon move Yes because you can remove the epsilon move and you will still have a NFA but may be with multiple final state and middle states but nevertheless it will be equivalent. It is reverse of Option C
0 votes
0 votes
A Language is said to be regular if there exists a DFA with a single final state i.e.,option D is the answer

Related questions

0 votes
0 votes
1 answer
2
Deepak9000 asked Nov 27, 2023
201 views
Why is C is regular as it non regular as?Please help me with this confusion
0 votes
0 votes
1 answer
3
M_Umair_Khan42900 asked Dec 29, 2022
743 views
Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b].s(a) p(pp)*( A + p)q + q and p*q(b) A +0(0+1)* + (0+1)* 00(0+1)...