The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

asked in Theory of Computation by Active (3.5k points) | 51 views
Is it c?
please explain
We know that Regular grammars can only be either right linear or left linear. If we can express a language in one of the form then we can convert it to the other form as well. So we can say that there exists both right and left linear grammar for regular languages. option a and b are true.

If we have an Epsilon-NFA there is always a way out to remove Epsilon transition and get an NFA which is Epsilon free. So e is also true.

The condition in d is not at all necessary for a language to be regular. We can have multiple final states in a DFA as the formal definition states so. So d is False.

Suppose you obtain an NFA having multiple final states. Then you can add Epsilon transition from each of them to another state and call it the new final state and make the previous final ones as non-final. Option c can be proved true in this way. (you can always remove epsilon moves to get epsilon free nfa)

2 Answers

+2 votes

Option c is right

  •  if a language is regular then there must exist a left linear and right linear grammar .so option a and b is true .

Example : L= a*

Left linear grammar is : s--->aS/null

Right linear grammar is: s---->Sa/null

  • In NFA if there is multiple final state then we can make it single final state . But not in DFA .

  • If a language is regular then there exist a NFA . AND NFA WITH NULL IS EQUIVALENT TO NFA . BECZ CONVERSION IS POSSIBLE . SO OPTION e is also true .

answered by Boss (25.3k points)
what is the significance of c and d statements?

While conversion of finite autometa to reguler expresion then we need to make single final state in NFA .


Thanks a lot!
0 votes
it's b.
answered by (11 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,894 questions
52,261 answers
67,679 users