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

asked in Theory of Computation by Active (1.4k points) | 42 views
0
Is it c?
0
please explain
+1
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 (23.3k points)
0
what is the significance of c and d statements?
+2

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

 

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


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

39,437 questions
46,622 answers
139,355 comments
57,007 users