1. Home
  2. GATE
  3. Computer Science and Information Technology
  4. Topics
  5. concept:regular-expressions
Computer Science and Information Technology

GATE CSE concept:regular-expressions PYQs

Build your understanding with focused practice from past exam papers.

Questions 11–12 of 12. Imported answers require independent review unless marked reviewed.

Topic practice 12 questionsPage 2 of 2

Question 22

Open question
CSNAT1 markNeeds review
Consider the language

given by the regular expression

over the alphabet

. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting

is ____________.

Log in to check the answer

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Question 41

Open question
CSMCQ2 marksNeeds review
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ∅? III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ? IV. Given a Turing machine M and a string w, is w ∈ L(M)?
Your answerChoose one option.

Log in to check the answer

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer