GATE Theory of Computation PYQ

GATE Theory of Computation PYQ

Q1➡ | GATE 2021 Set-1
Suppose that L1is a regular language and L2is a context free language. Which one of the following languages is NOT necessarily context free?
i ➥ L1. L2
ii ➥ L1 − L2
iii ➥ L1 ∩ L2
iv ➥ L1 ∪ L2

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Closure Property Help-Line

Q2➡ | GATE 2021 Set-1
Let denote an encoding of an automaton M. Suppose that Σ = {0,1}. Which of the following languages is/are NOT recursive?
i ➥ L = { | M is a PDA such that L(M) = ∅}
ii ➥ L = { | M is a PDA such that L(M) = Σ*}
iii ➥ L = { | M is a DFA such that L(M) = Σ*}
iv ➥ L = { | M is a DFA such that L(M) = ∅}

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRecursive Language Help-Line

Q3➡ | GATE 2021 Set-1
For a Turing machine M, denotes an encoding of M. Consider the following two languages.
L1=〈M〉|M takes more than 2021 steps on all inputs
L2=〈M〉|M takes more than 2021 steps on some input
Which one of the following options is correct?
i ➥ L1 is undecidable and L2 is decidable.
ii ➥ Both L1and L2 are decidable.
iii ➥ Both L1and L2 are undecidable.
iv ➥ L1 is decidable and L2 is undecidable.

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDecidability and UndecidabilityHelp-Line

Q4➡ | GATE 2021 Set-1
Consider the following language.
L={w ∈{0,1}* | ends with the sub-string 011}
Which one of the following deterministic finite automata accepts L ?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDFA Help-Line

Q5➡ | GATE 2021 Set-1

The number of strings of length 100 accepted by the above pushdown automaton is _____.

Show Answer With Best Explanation

Answer: 50
Explanation: Upload Soon

More DiscussionExplanation On YouTubePush Down Automata Help-Line

Q6➡ | GATE 2021 Set-2
Let L ⊆ {0, 1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?
i ➥ {0,1}* -L
ii ➥ L.L
iii ➥ L- {01}
iv ➥ L U {01}

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDeteministic Finite AutomataHelp-Line

Q6➡ | GATE 2021 Set-2
Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context free?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: I, II, IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTopic Help-Line

Q7➡ | GATE 2021 Set-2
Consider the following deterministic finite automaton (DFA).

The number of strings of length 8 accepted by the above automaton is ________.

Show Answer With Best Explanation

Answer: 256
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDFA Help-Line

Q8➡ | GATE 2021 Set-2
Suppose we want to design a synchronous circuit that processes a string of 0’s and 1’s. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1’s by a 0.
Consider the following example.
Input sequence: 00100011000011100
Output sequence: 00000001000001100

A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.
The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively.
Assume the initial state of the mealy machine is 0.
What are the Boolean expressions corresponding to t and y in terms of s and b?
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeMealy and Moore MachineHelp-Line

Q9➡ | GATE 2021 Set-2
Consider the following two statements about regular languages:
S1: Every infinite regular language contains an undecidable language as a subset.
S2: Every finite language is regular.
Which one of the following choices is correct?
i ➥ Both S1 and S2 are true.
ii ➥ Neither S1 nor S2 is true.
iii ➥ Only S1 is true.
iv ➥ Only S2 is true.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Language Help-Line

Q10➡ | GATE 2021 Set-2
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string ∊ is divisible by three.
i ➥ (0+11+11(1+00)*00)*
ii ➥ (0+1 (01*0)*1)*
iii ➥ (0+11+10(1+00)*01)*
iv ➥ (0*(1(01*0)*1)*)*

Show Answer With Best Explanation

Answer: II, III, IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Expression Help-Line

Q11➡ | GATE 2021 Set-2
For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR= 10110. Which of the following languages is/are context-free?
i ➥ L={w x wR | w, x ∈ {0,1}* }
ii ➥ L={w x xR wR | w, x ∈ {0,1}* }
iii ➥ L={w x wR xR | w, x ∈ {0,1}* }
iv ➥ L={w wR x xR | w, x ∈ {0,1}* }

Show Answer With Best Explanation

Answer: I, II, IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeContext Free Language Help-Line

Q12➡ | GATE 2020
Consider the language L = {an| n≥0} ∪ {anbn| n≥0} and the following statements.
I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE?
i ➥ III only
ii ➥ I only
iii ➥ I and III only
iv ➥ II only

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Language and Grammers Help-Line

Q13➡ | GATE 2020
Consider the following statements.
I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
i ➥ II only
ii ➥ I only
iii ➥ Neither I nor II
iv ➥ Both I and II

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Language Help-Line

Q14➡ | GATE 2020
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
i ➥ (0*10*10*)*0*1
ii ➥ 10*(0*10*10*)*
iii ➥ (0*10*10*)*10*
iv ➥ ((0 + 1)*1(0 + 1)*1)*10*

Show Answer With Best Explanation

Answer: Marks to All
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Expression Help-Line

Q15➡ | GATE 2020
Consider the following languages.
L1 = {wxyx | w,x,y ∈ (0 + 1)+}
L2 = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}
Which one of the following is TRUE?
i ➥ L1 is context-free but L2 is not context-free.
ii ➥ L1 is regular and L2 is context-free.
iii ➥ Neither L1 nor L2 is context-free.
iv ➥ L1 is context-free but not regular and L2 is context-free.

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLanguages and GrammersHelp-Line

Q16➡ | GATE 2020
Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.
L1 = {<M>| L(M) = Φ}
L2 = {<M,w,q>| M on input w reaches state q in exactly 100 steps}
L3 = {<M>| L(M) is not recursive}
L4 = {<M>| L(M) contains at least 21 members}
i ➥ L2, L3 and L4 only
ii ➥ L1, L3 and L4 only
iii ➥ L2 and L3 only
iv ➥ L1 and L3 only

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDecidability & UndecidabilityHelp-Line

Q17➡ | GATE 2020
Consider the following language.
L = {x ∈ {a,b}* | number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is ______.

Show Answer With Best Explanation

Answer: 6
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite Automata Help-Line

Q18➡ | GATE 2019
If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?
i ➥ L∙LR = {xy │ x ∈ L, yR ∈ L}
ii ➥ Suffix (L) = {y ∈ Σ*|∃y ∈ Σ* such that xy ∈ L}
iii ➥ Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L}
iv ➥ {wwR │w ∈ L}

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Language Help-Line

Q19➡ | GATE 2019
For Σ = {a,b}, let us consider the regular language L = {x|x = a2+3k or x = b10+12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
i ➥ 5
ii ➥ 24
iii ➥ 9
iv ➥ 3

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Language Help-Line

Q20➡ | GATE 2019
Consider the following sets:

S1. Set of all recursively enumerable languages over the alphabet {0,1}
S2. Set of all syntactically valid C programs
S3. Set of all languages over the alphabet {0,1}
S4. Set of all non-regular languages over the alphabet {0,1}

Which of the above sets are uncountable?
i ➥ S1 and S2
ii ➥ S3 and S4
iii ➥ S2 and S3
iv ➥ S1 and S4

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeCountability Help-Line

Q21➡ | GATE 2019
Which one of the following languages over Σ = {a,b} is NOT context-free?
i ➥ {wanbnwR |w ∈ {a,b}*, n ≥ 0}
ii ➥ {anbi | i ∈ {n, 3n, 5n}, n ≥ 0}
iii ➥ {wanwRbn |w ∈ {a,b}*, n ≥ 0}
iv ➥ {wwR |w ∈ {a,b}*}

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeContext Free LanguageHelp-Line

Q22➡ | GATE 2019
Let Σ be the set of all bijections from {1, …, 5} to {1, …, 5}, where id denotes the identity function i.e. id( j ) = j,∀j. Let º denote composition on functions. For a string x = x1 x2 … xn ∈ Σn, n ≥ 0. Let π(x) = x1 º x2 º º xn.
Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of states in any DFA accepting L is _________.

Show Answer With Best Explanation

Answer: 120
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite Automata Help-Line

Q23➡ | GATE 2018
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
i ➥ k ≤ n2
ii ➥ k ≤ 2n
iii ➥ k ≥ 2n
iv ➥ k ≥ n

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube NFA/DFA Help-Line

Q24➡ | GATE 2018
The set of all recursively enumerable languages is
i ➥ closed under complementation.
ii ➥ closed under intersection.
iii ➥ a subset of the set of all recursive languages.
iv ➥ an uncountable set.

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Closure-Property Help-Line

Q25➡ | GATE 2018
i ➥ I and IV only
ii ➥ I and II only
iii ➥ II and III only
iv ➥ II and IV only

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeContext Free Language Help-Line

Q26➡ | GATE 2018
Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.
(I) For an unrestricted grammar G and a string w, whether w∈L(G)
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammar G1 and G2 whether L(G1 )=L(G2)
(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language
Which one of the following statement is correct?
i ➥ Only I and II are undecidable
ii ➥ Only III is undecidable
iii ➥ Only II and IV are undecidable
iv ➥ Only I, II and III are undecidable

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTube Undecidability Help-Line

Q27➡ | GATE 2018
Given a language L, define Li as follows:
L0 = {ε}
Li = Li-1 L for all i>0
The order of a language L is defined as the smallest k such that Lk = Lk+1.
Consider the language L1 (over alphabet 0) accepted by the following automaton.


The order of L1 is __.

Show Answer With Best Explanation

Answer: 2
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite Automata Help-Line

Q28➡ | GATE 2017 Set-1
Consider the following context-free grammar over the alphabet Σ = {a, b, c} with S as the start symbol:
S → abScT | abcT
T → bT | b
Which one of the following represents the language generated by the above grammar?
i ➥ {(ab)n (cbn)m│m,n ≥ 1}
ii ➥ {(ab)n (cb)n│n ≥ 1}
iii ➥ {(ab)n (cbm)n│m,n ≥ 1}
iv ➥ {(ab)n cbm1 cbm2 …cbmn │n,m1,m2,…,mn ≥ 1}

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTube Context Free Grammer Help-Line

Q29➡ | GATE 2017 Set-1
Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a,b}. The smallest number of states needed in deterministic finite-state automation (DFA) accepting L is ________.

Show Answer With Best Explanation

Answer: 4.0
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite Automata Help-Line

Q30➡ | GATE 2017 Set-1
Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.
G1: S → aSb|T, T → cT|ϵ
G2: S → bSa|T, T → cT|ϵ
The language L(G1) ∩ L(G2) is
i ➥ Context-Free but not regular
ii ➥ Recursive but not context-free
iii ➥ Finite
iv ➥ Not finite but regular

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeContext Free GrammerHelp-Line

Q31➡ | GATE 2017 Set-1
If G is a grammar with productions
S → SaS | aSb | bSa | SS | ϵ
where S is the start variable, then which one of the following strings is not generated by G?
i ➥ babba
ii ➥ abbaa
iii ➥ abab
iv ➥ aaab

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeGrammer Help-Line

Q32➡ | GATE 2017 Set-1
Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A, always halts with f(x) on its tape. Let Lf denote the language {x # f(x)│x ∈ A*}. Which of the following statements is true:
i ➥ If f is computable then Lf is recursively enumerable, but not conversely.
ii ➥ If f is computable then Lf is recursive, but not conversely.
iii ➥ f is computable if and only if Lf is recursive.
iv ➥ f is computable if and only if Lf is recursively enumerable.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeComputability Help-Line

Q33➡ | GATE 2017 Set-1
Consider the following languages over the alphabet Σ = {a, b, c}.
Let L1 = {an bn cm│m,n ≥ 0} and L2 = {am bn cn│m,n ≥ 0}

Which of the following are context-free languages?
I. L1∪ L2
II. L1∩ L2
i ➥ II only
ii ➥ I only
iii ➥ Neither I nor II
iv ➥ I and II

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeContext Free Language Help-Line

Q34➡ | GATE 2017 Set-2
Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?
I. L1 U L2 is context Free.
II.
III. L1 – R is context Free.
IV.
i ➥ I only
ii ➥ I, II and IV only
iii ➥ II and IV only
iv ➥ I and III only

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTube Context Free language Help-Line

Q35➡ | GATE 2017 Set-2
Identify the language generated by the following grammar, where S is the start variable.
S → XY
X → aX|a
Y → aYb|ϵ
i ➥ {am bn │ m ≥ n, n > 0}
ii ➥ {am bn │ m ≥ n, n ≥ 0}
iii ➥ {am bn │ m > n, n ≥ 0}
iv ➥ {am bn │ m > n, n > 0}

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite Automata Help-Line

Q36➡ | GATE 2017 Set-2
The minimum possible number of a deterministic finite automation that accepts the regular language L = {w1aw2 | w1, w2 ∈ {a,b}*, |w1| = 2,|w2| ≥ 3} is ___________.

Show Answer With Best Explanation

Answer: 8
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDFA Help-Line

Q37➡ | GATE 2017 Set-2
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)?
i ➥ III and IV only
ii ➥ II, III and IV only
iii ➥ II and III only
iv ➥ I and IV only

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDecidability and UndecidabilityHelp-Line

Q38➡ | GATE 2017 Set-2
Consider the following languages:
L1 = {ap│p is a prime number}
L2 = {an bmc2m | n ≥ 0, m ≥ 0}
L3 = {an bn c2n │ n ≥ 0} 
L4 = {an bn │ n ≥ 1}
Which of the following are CORRECT?
I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3 is not context-free but recursive. 
IV. L4 is deterministic context-free.
i ➥ III and IV only
ii ➥ I and IV only
iii ➥ II and III only
iv ➥ I, II and IV only

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeContext Free LanguageHelp-Line

Q39➡ | GATE 2017 Set-2
Let δ denote the transition function and denote the extended transition function of the ε-NFA whose transition table is given below:

Then is
i ➥ {q0,q2,q3}
ii ➥ {q0,q1,q2}
iii ➥ {q0,q1,q3}
iv ➥

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeNFA Help-Line

Q40➡ | GATE 2016 Set-1
Which of the following languages is generated by the given grammar?
S→ aS|bS|ε
i ➥ {a,b}*
ii ➥ {an |n ≥ 0} U {bn |n ≥ 0} U {an bn|n ≥ 0}
iii ➥ {w ∈ {a,b}* | w has equal number of a’s and b’s}
iv ➥ {anbm |n,m ≥ 0}

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLanguage Help-Line

Q41➡ | GATE 2016 Set-1
Which of the following decision problems are undecidable?
• I. Given NFAs N1 and N2, is L(N1)∩L(N2)= Φ?
• II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
• III. Given CFGs G1 and G2, is L(G1) = L(G2)?
• IV. Given a TM M, is L(M) = Φ?
i ➥ II and IV only
ii ➥ III and IV only
iii ➥ II and III only
iv ➥ I and IV only

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDecidability and Undecidability Help-Line

Q42➡ | GATE 2016 Set-1
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
i ➥ 00(0 + 1)* 11 + 11(0 + 1)* 00
ii ➥ (0 + 1)* 00(0 + 1)* + (0 + 1)* 11(0 + 1)*
iii ➥ (0 + 1)* (00(0 + 1)* 11 + 11(0 + 1)* 00)(0 + 1)*
iv ➥ (0 + 1)* 0011(0 + 1)* + (0 + 1)* 1100(0 + 1)*

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Expressions Help-Line

Q42➡ | GATE 2016 Set-1
Consider the following context-free grammars:
G1: S → aS|B, B → b|bB
G2: S → aA|bB, A → aA|B|ε, B → bB|ε
Which one of the following pairs of languages is generated by G1 and G2, respectively?
i ➥ {am bn│m > 0 or n > 0} and {am bn |m > 0 and n > 0}
ii ➥ {am bn│m > 0 and n > 0} and {am bn |m > 0 or n≥0}
iii ➥ {am bn│m≥0 or n > 0} and {am bn |m > 0 and n > 0}
iv ➥ {am bn│m≥0 and n > 0} and {am bn |m > 0 or n > 0}

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeContext Free LanguageHelp-Line

Q43➡ | GATE 2016 Set-1
Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?
i ➥ L = {an bn│n ≥ 0} and is not accepted by any finite automata
ii ➥ L = {an |n≥0} ∪ {anbn|n ≥ 0} and is not accepted by any deterministic PDA
iii ➥ L is not accepted by any Turing machine that halts on every input
iv ➥ L = {an |n ≥ 0} ∪ {an bn |n ≥ 0} and is deterministic context-free

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubePush Down Automata Help-Line

Q44➡ | GATE 2016 Set-2
The number of states in the minimum sized DFA that accepts the language defined by the regular expression
(0+1)*(0+1) (0+1)* is_________.

Show Answer With Best Explanation

Answer: 2
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDFA Help-Line

Q45➡ | GATE 2016 Set-2
Language L1 is defined by the grammar: S1 → aS1b|ε
Language L2 is defined by the grammar: S2 → abS2|ε
Consider the following statements:
• P: L1 is regular
• Q: L2 is regular
Which one of the following is TRUE?
i ➥ Both P and Q are true
ii ➥ P is true and Q is false
iii ➥ P is false and Q is true
iv ➥ Both P and Q are false

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Language Help-Line

Q46➡ | GATE 2016 Set-2
Consider the following types of languages: L1: Regular, L2: Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?
i ➥ I only
ii ➥ I and III only
iii ➥ I and IV only
iv ➥ I, II and III only

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeClosure Property Help-Line

Q47➡ | GATE 2016 Set-2
Consider the following two statements:
I: If all states of an NFA are accepting states then the language accepted by the NFA is Σ*.
II: There exists a regular language A such that for all languages B, A∩B is regular.
Which one of the following is CORRECT?
i ➥ Only I is true
ii ➥ Only II is true
iii ➥ Both I and II are true
iv ➥ Both I and II are false

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite Automata and Regular LanguageHelp-Line

Q48➡ | GATE 2016 Set-2
Consider the following languages:
• L1= {an bm cn+m : m,n ≥ 1}
• L2= {an bn c2n : n ≥ 1}
Which one of the following is TRUE?
i ➥ Both L1 and L2 are context-free.
ii ➥ L1 is context-free while L2 is not context-free.
iii ➥ L2 is context-free while L1 is not context-free.
iv ➥ Neither L1 nor L2 is context-free.

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeContext Free Language Help-Line

Q49➡ | GATE 2016 Set-2
Consider the following languages.
• L1 = {〈M〉|M takes at least 2016 steps on some input},
• L2 = {〈M〉│M takes at least 2016 steps on all inputs} and
• L3 = {〈M〉|M accepts ε},
where for each Turing machine M, 〈M〉 denotes a specific encoding of M. Which one of the following is TRUE?
i ➥ L1 is recursive and L2, L3 are not recursive
ii ➥ L2 is recursive and L1, L3 are not recursive
iii ➥ L1, L2 are recursive and L3 is not recursive
iv ➥ L1, L2, L3 are recursive

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRecursive Language Help-Line

Q50➡ | GATE 2015 Set-1
For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?

I. L’1 (Complement of L1) is recursive.
II. L’2 (Complement of L2) is recursive.
III. L’1 is context Free
IV. L’1 U L2 is recursive Enumerable.
i ➥ I only
ii ➥ III only
iii ➥ III and IV only
iv ➥ I and IV only

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLanguages Help-Line

Q51➡ | GATE 2015 Set-1


Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is _____.

Show Answer With Best Explanation

Answer: 1
Explanation: Upload Soon

More DiscussionExplanation On YouTubeDFA Help-Line

Q52➡ | GATE 2015 Set-1
Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows:

Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
i ➥ 10110
ii ➥ 10010
iii ➥ 01010
iv ➥ 01001

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubePDA Help-Line

Q53➡ | GATE 2015 Set-2
Consider the following statements:
I. The complement of every Turning decidable language is Turning decidable
II. There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable
Which of the above statements is/are True?
i ➥ Only II
ii ➥ Only III
iii ➥ Only I and II
iv ➥ Only I and III

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More Discussion Explanation On YouTube Decidability and UndecidabilityHelp-Line

Q54➡ | GATE 2015 Set-2
The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is ________.

Show Answer With Best Explanation

Answer: 3
Explanation: Upload Soon

More DiscussionExplanation On YouTube DFA Help-Line

Q55➡ | GATE 2015 Set-2
Which of the following language is/are regular ?
L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w
L2: {anbm ⎪m ≠ n and m, n≥0}
L3: {apbqcr ⎪ p, q, r ≥ 0}
i ➥ L1 and L3 only
ii ➥ L2 only
iii ➥ L2 and L3 only
iv ➥ L3 only

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTube Regular Language Help-Line

Q56➡ | GATE 2015 Set-2
Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1 and X2 are related as follows:
X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}
Which one of the following choices precisely represents the strings in X0?
i ➥ 10(0* + (10)*) 1
ii ➥ 10(0* + (10)*)*1
iii ➥ 1(0 + 10)* 1
iv ➥ 10(0 + 10)* 1 + 110(0 + 10)* 1

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Grammer Help-Line

Q57➡ | GATE 2015 Set-3
consider the equality and the following choices for X
I. θ(n4)
II. θ(n5)
III. Ο(n5)
IV. Ω(n3)
The equality above remains correct if X is replaced by
i ➥ Only I
ii ➥ Only II
iii ➥ I or III or IV but not II
iv ➥ II or III or IV but not I

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More Discussion Explanation On YouTube Decidability and UndecidabilityHelp-Line

Q58➡ | GATE 2015 Set-3
Let L be the language represented by the regular expression Σ*0011Σ* where Σ = {0,1}. What is the minimum number of states in a DFA that recognizes L’ (complement of L)?
i ➥ 4
ii ➥ 5
iii ➥ 6
iv ➥ 8

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Expression Help-Line

Q59➡ | GATE 2015 Set-3
Which of the following languages are context-free?
L1 = {ambnanbm ⎪ m, n ≥ 1}
L2 = {ambnambn ⎪ m, n ≥ 1}
L3 = {ambn ⎪ m = 2n + 1}
i ➥ L1 and L2 only
ii ➥ L1 and L3 only
iii ➥ L2 and L3 only
iv ➥ L3 only

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Context Free Language Help-Line

Q60➡ | GATE 2014 Set-1
Which one of the following is TRUE?
i ➥ The language L={an bn│n≥0} is regular.
ii ➥ The language L={an│n is prime} is regular.
iii ➥ The language L={w│w has 3k+1b’s for some k∈N with Σ={a,b} } is regular.
iv ➥ The language L={ww│w∈Σ* with Σ={0,1} } is regular.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular LanguagesHelp-Line

Q61➡ | GATE 2014 Set-1
Consider the finite automaton in the following figure

What is the set of reachable states fot the input string 0011?
i ➥ {q0,q1,q2 }
ii ➥ {q0,q1 }
iii ➥ {q0,q1,q2,q3 }
iv ➥ {q3 }

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite-AutomataHelp-Line

Q62➡ | GATE 2014 Set-1
Which one of the following is TRUE?
i ➥ The language L={an bn│n≥0} is regular.
ii ➥ The language L={an│n is prime} is regular.
iii ➥ The language L={w│w has 3k+1b’s for some k∈N with Σ={a,b} } is regular.
iv ➥ The language L={ww│w∈Σ* with Σ={0,1} } is regular.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular LanguagesHelp-Line

Q63➡ | GATE 2014 Set-1
Consider the finite automaton in the following figure

What is the set of reachable states fot the input string 0011?
i ➥ {q0,q1,q2 }
ii ➥ {q0,q1 }
iii ➥ {q0,q1,q2,q3 }
iv ➥ {q3 }

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite-AutomataHelp-Line

Q64➡ | GATE 2014 Set-1
Let L be a language and L¯ be its complement. Which one of the following is NOT a viable possibility?
i ➥ Neither L nor L¯ is recursively enumerable (r.e.).
ii ➥ One of L and L¯ is r.e. but not recursive; the other is not r.e.
iii ➥ Both L and L¯ are r.e. but not recursive.
iv ➥ Both L and L¯ are recursive.

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube ClosureHelp-Line

Q65➡ | GATE 2014 Set-1
Which of the regular expressions given below represent the following DFA?

I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1
i ➥ I and II only
ii ➥ I and III only
iii ➥ II and III only
iv ➥ I, II, and III

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Regular Language Help-Line

Q66➡ | GATE 2014 Set-2

If L1 = {an| n ≥ 0} and L2= {bn| n ≥ 0}, consider

(I) L1.L2 is a regular language
(II) L1.L2 = {anbn|n ≥ 0}

Which one of the following is CORRECT?
i ➥ Only (I)
ii ➥ Only (II)
iii ➥ Both (I) and (II)
iv ➥ Neither (I) nor (II)

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular LanguagesHelp-Line

Q67➡ | GATE 2014 Set-2
Let A ≤N B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?
i ➥ If A ≤N B and B is recursive then A is recursive.
ii ➥ If A ≤N B and A is undecidable then B is undecidable.
iii ➥ If A ≤N B and B is recursively enumerable then A is recursively enumerable.
iv ➥ If A ≤N B and B is not recursively enumerable then A is not recursively enumerable

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeReducibleHelp-Line

Q68➡ | GATE 2014 Set-2
Let < M > be the encoding of a Turing machine as a string over Z = {0, 1}. Let
L = { < M > | M is a Turing macℎine tℎat accepts a string of length 2014 }. Then, L is
i ➥ decidable and recursively enumerable
ii ➥ undecidable but recursively enumerable
iii ➥ undecidable and not recursively enumerable
iv ➥ decidable but not recursively enumerable

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Turing machineHelp-Line

Q69➡ | GATE 2014 Set-3
Let L1 = {w ∈ {0,1} | w has at least as many occurrences of (110)’s as (011)’s}. Let L2 = {w ∈ {0,1} | w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?
i ➥ L1 is regular but not L2
ii ➥ L2 is regular but not L1
iii ➥ Both L1 and L2 are regular
iv ➥ Neither L1 nor L2 are regular

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular LanguageHelp-Line

Q70➡ | GATE 2014 Set-3
The length of the shortest string NOT in the language (over Σ = {a b,}) of the following regular is expression is _______.
a*b*(ba)*a*

Show Answer With Best Explanation

Answer: 3
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Expression Help-Line

Q71➡ | GATE 2014 Set-3
Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ. Which one of the following is TRUE?
i ➥ Both 2Σ and Σ* are countable
ii ➥ 2Σ* is countable and Σ* is uncountable
iii ➥ 2Σ* is uncountable and Σ* is countable
iv ➥ Both 2Σ* and Σ* are uncountable

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeCountability Help-Line

Q72➡ | GATE 2014 Set-3
Which one of the following problems is undecidable?
i ➥ Deciding if a given context-free grammar is ambiguous.
ii ➥ Deciding if a given string is generated by a given context-free grammar.
iii ➥ Deciding if the language generated by a given context-free grammar is empty.
iv ➥ Deciding if the language generated by a given context-free grammar is finite.

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTube undecidableHelp-Line

Q73➡ | GATE 2014 Set-3
Consider the following languages over the alphabet Σ = {0,1, c}:
L1 = {0n1n | n ≥ 0}
L2 = {wcwr |w ∈ {0,1}}
L3 = {wwr |w ∈ {0,1}}
Here, wr is the reverse of the string w. Which of these languages are deterministic Context-free languages?
i ➥ None of the languages
ii ➥ Only L1
iii ➥ Only L1 and L2
iv ➥ All the three languages

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Regular Language Help-Line

Q74➡ | GATE 2013
Consider the languages L1 = ϕ and L2 = {a}. Which one of the following represents L1L2* ∪ L1?
i ➥ {є}
ii ➥ ϕ
iii ➥ a
iv ➥ {є,a}

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTube Regular Language Help-Line

Q75➡ | GATE 2013
Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.
i ➥ 1 and 4 only
ii ➥ 1 and 3 only
iii ➥ 2 only
iv ➥ 3 only

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTubeTurning Machine Help-Line

Q76➡ | GATE 2013
Consider the following languages.
L1 = {0p1q0r | p,q,r≥0}
L2 = {0p1q0r | p,q,r≥0, p≠r}
Which one of the following statements is FALSE?
i ➥ L2 is context-free.
ii ➥ L1∩ L2 is context-free.
iii ➥ Complement of L2 is recursive.
iv ➥ Complement of L1 is context-free but not regular.

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeLanguage Help-Line

Q77➡ | GATE 2013
Consider the DFA given:

Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.
i ➥ 1 and 3 only
ii ➥ 2 and 4 only
iii ➥ 2 and 3 only
iv ➥ 3 and 4 only

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeRegular Language Help-Line

Q78➡ | GATE 2013
Which of the following is/are undecidable?
G is a CFG. Is L(G) = Φ?
G is a CFG. Is L(G) = Σ*?
M is a Turing machine. Is L(M) regular?
A is a DFA and N is an NFA. Is L(A) = L(N)?
i ➥ 3 only
ii ➥ 3 and 4 only
iii ➥ 1, 2 and 3 only
iv ➥ 2 and 3 only

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeUndecidability Help-Line

Q79➡ | GATE 2012
What is the complement of the language accepted by the NFA shown below?
Assume Σ={a} and ε is the empty string.
i ➥
ii ➥ {ε}
iii ➥ a*
iv ➥ {a ,ε}

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More Discussion Explanation On YouTube Finite Automata Help-Line

Q80➡ | GATE 2012
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a context-free language, then, is L’ also context-free?
3) If L is a regular language, then, is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?
i ➥ 1, 2, 3, 4
ii ➥ 1, 2
iii ➥ 2, 3, 4
iv ➥ 3, 4

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTube Decidability Help-Line

Q81➡ | GATE 2012
Given the language L ={ab,aa,baa}, which of the following strings are in L* ?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
i ➥ 1, 2 and 3
ii ➥ 2, 3 and 4
iii ➥ 1, 2 and 4
iv ➥ 1, 3 and 4

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Regular Language Help-Line

Q82➡ | GATE 2012
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is
shown below.

The missing arcs in the DFA are
i ➥
ii ➥
iii ➥
iv ➥

Show Answer With Best Explanation

Answer: IV
Explanation: Upload Soon

More DiscussionExplanation On YouTubeFinite Automata Help-Line

Q83➡ | GATE 2011
Which of the following pairs have DIFFERENT expressive power?
i ➥ Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
ii ➥ Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)
iii ➥ Deterministic single-tape Turning machine and Non-deterministic single tape Turning machine
iv ➥ Single-tape Turning machine and multi-tape Turning machine

Show Answer With Best Explanation

Answer: II
Explanation: Upload Soon

More DiscussionExplanation On YouTube Expressive Power Help-Line

Q84➡ | GATE 2011
Let P be a regular language and Q be a context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be [pnqn | n ∈ N]). Then which of the following is ALWAYS regular?
i ➥ P ∩ Q
ii ➥ P – Q
iii ➥ Σ* – P
iv ➥ Σ* – Q

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Regular Language Help-Line

Q85➡ | GATE 2011
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0:n-1] is given below. Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array
Initialize Ln-1=1.
For all i such that 0≤i≤n-2

Finally the length of the longest monotonically increasing sequence is Max(L0, L1, …, Ln-1).
Which of the following statements is TRUE?
i ➥ The algorithm uses dynamic programming paradigm
ii ➥ The algorithm has a linear complexity and uses branch and bound paradigm
iii ➥ The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
iv ➥ The algorithm uses divide and conquer paradigm

Show Answer With Best Explanation

Answer: I
Explanation: Upload Soon

More DiscussionExplanation On YouTube Dynamic Programming Help-Line

Q86➡ | GATE 2011
Consider the languages L1,L2 and L3 as given below.
L1 = {0p1q | p,q∈N},
L2 = {0p1q | p,q∈N and p=q} and
L3 = {0p1q0r | p,q,r∈N and p=q=r}.
Which of the following statements is NOT TRUE?
i ➥ Push Down Automate (PDA) can be used to recognize L1 and L2
ii ➥ L1 is a regular language
iii ➥ All the three languages are context free
iv ➥ Turing machines can be used to recognize all the languages

Show Answer With Best Explanation

Answer: III
Explanation: Upload Soon

More DiscussionExplanation On YouTube Language Help-Line

Q87➡ | GATE 2011
Definition of a language L with alphabet {a} is given as following.
L = {ank| k>0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
i ➥ k+1
ii ➥ n+1
iii ➥ 2n+1
iv ➥ 2k+1