That's a perfect explanation.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+5 votes

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

- Myhill-Nerode theorem
- Pumping lemma
- Drawing an NFA
- 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

+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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,560 answers

146,291 comments

62,306 users