Register

Regular Language

5,241 views
9 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 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 1 vote
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 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
Voting & Accepting an answer helps improve the community
← Previous · permutationNext → · co
← Previous in category · Complement of a recu...Next in category → · PDA
Position:
Show:

Related questions

0 0 votes
1 1 answer
85
85 views
GO Classes asked Oct 1
85 views
GO Classes DPP | GATE CS | Theory of Computation | Regular-Language Non-Emptiness
Which of the following is true?There is no known algorithm for checking whether a regular language is nonempty. The proof of the pumping lemma was a proof by induction. T...
2 2 votes
1 1 answer
102
102 views
GO Classes asked Sep 21
102 views
GO Classes DPP | GATE CS | Theory of Computation | Regular Language
Let $M$ and $N$ be two DFAs. Define$$Z=\{u_1v_1u_2v_2\cdots u_kv_k : k\ge0, ~u_i\in L(M), ~v_i\in L(N)\}.$$Which regular-language expression describes $Z$?$L(M)^*L(N)^*$ ...
0 0 votes
1 1 answer
82
82 views
GO Classes asked Sep 21
82 views
GO Classes DPP | GATE CS | Theory of Computation | Regular Language
For an arbitrary language $L$, which of the following statements is correct?If $L^*$ is regular, then $L$ must be regular. If $L$ is nonregular, then $L^*$ must be nonreg...
1 1 vote
1 1 answer
89
89 views
GO Classes asked Sep 16
89 views
GO Classes DPP | GATE CS | Theory of Computation | Regular Language
Let $L=\{w\in{0,1}^*\mid w$ contains equal numbers of substrings $01$ and $10\}$. Which statements are correct?$L$ is regular. A correct regular expression for $L$ is $\e...