The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
325 views

Which of the following are useful in proving a language to be regular?

  1. Myhill-Nerode theorem
  2. Pumping lemma
  3. Drawing an NFA
  4. Forming a regular expression

(A) All of these

(B) 1, 3 and 4 only

(C) 2, 3 and 4 only

(D) 3 and 4 only

asked in Theory of Computation by Veteran (400k points)
retagged by | 325 views

2 Answers

+10 votes
Best answer

(B)1, 3 and 4 only

As from the given options, Myhill-Nerode theorem is useful by providing necessary and sufficient condition for proving that a language regular. Pumping lemma is often used to prove that a language is non-regular. Drawing an NFA can be useful to prove a language is regular. Forming a regular expression can also help us prove if it is a regular language

 

answered by Loyal (6.1k points)
selected by
0
That's a perfect explanation.
0
all options are right
+1
No. Pumping lemma cannot say if a language is regular. If pumping lemma is violated, it can say a language is not regular. But if pumping lemma is satisfied, it doesn't mean language is regular.
0 votes
  • The Myhill-Nerode theorem is an important characterization of regular languages. and is is used for regular language.
  •  
  • pumping lemma is a negativity test and it is used for non regular.
  •  
  • if you drow a dfa . then the language is regular .
  •  
  • if you forming a regular expression .then the language is regular

so option 1,3,4 is right

answered by Boss (33.7k 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
49,443 questions
53,648 answers
186,099 comments
70,909 users