Skip to content
GATETECH

GATE CS Regular and Context-free Languages questions

Practise Regular and Context-free Languages questions for GATE CS. Explore official PYQs and original topic-wise quizzes, check answers and view available solutions. Free, no sign-in.

Subject, topic, year and type filter the full library. Match any choice within a filter, and all selected filter categories. Search, source and sort apply to this page.

20 on this page
Official PYQ2009Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Let πA\pi_A be a problem that belongs to the class NP. Then which one of the following is TRUE?
Official PYQ2008Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Which of the following are regular sets? {anb2m∣n≥0,m≥0}\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\} {anbm∣n=2m}\left\{a^nb^m \mid n =2m \right\} {anbm∣n≠m}\left\{a^nb^m \mid n \neq m \right\} {xcy∣x,y,∈{a,b}∗}\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}
Official PYQ2008Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Match the following: …
Official PYQ2008Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Which of the following is true for the language {ap∣p is a prime }?\left\{ a^p \mid p \text{ is a prime } \right \}?
Official PYQ2007Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
The language L={0i21i∣i≥0}L=\left\{0^i21^i \mid i \geq 0\right\} over the alphabet {0,1,2}\left\{0, 1, 2\right\} is:
Official PYQ2007Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Which of the following languages is regular?
Official PYQ2007Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Which of the following is TRUE?
Official PYQ2006Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Let L1L_1 be a regular language, L2L_2 be a deterministic context-free language and L3L_3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?
Official PYQ2006Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Let SHAM3_3 be the problem of finding a Hamiltonian cycle in a graph G=(V,E)G=(V,E) with ∣V∣|V| divisible by 33 and DHAM3_3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
Official PYQ2006Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
For s∈(0+1)∗s\in (0+1)^{*} let d(s)d(s) denote the decimal value of s(s (e.g. d(101)=5).d (101) = 5 ). Let L={s∈(0+1)∗∣d(s) mod 5=2 and d(s) mod 7≠4}L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}Which one of the following statements is true?
Official PYQ2006Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
If ss is a string over (0+1)∗(0+1)^* then let n0(s)n_0(s) denote the number of 00’s in ss and n1(s)n_1(s) the number of 11’s in ss. Which one of the following languages is not regular?
Official PYQ2005Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Consider the languages: L1={anbncm∣n,m>0}L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\} and L2={anbmcm∣n,m>0}L_2 = \left\{a^nb^mc^m\mid n, m > 0\right\} Which one of the following statements is FALSE?
Official PYQ2004Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
The language {ambncm+n∣m,n≥1}\left\{a^mb^nc^{m+n} \mid m, n \geq1\right\} is
Official PYQ2002Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Which of the following is true?
Official PYQ2002Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
The language accepted by a Pushdown Automaton in which the stack is limited to 1010 items is best described as
Official PYQ2001Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Consider the following languages: L1={ww∣w∈{a,b}∗}L1=\left\{ww \mid w \in \{a,b\}^*\right\} L2={wwR∣w∈{a,b}∗,wR is the reverse of w}L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\} L3={02i∣ i is an integer}L3=\left\{0^{2i} \mid \text{ i is an integer} \right\} L4={0i2∣ i is an integer}L4= \left\{ 0^{i^2} \mid \text{ i is an integer} \right\} Which of the languages are regular?
Official PYQ2001Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Consider the following two statements: S1:{02n∣n≥1}S_1: \left\{ 0^{2n} \mid n \geq 1 \right\} is a regular language S2:{0m1n0m+n∣m≥1 and n≥1}S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \right\} is a regular language Which of the following statement is correct?
Official PYQ2000Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
What can be said about a regular language LL over {a}\{ a \} whose minimal finite state automaton has two states?
Official PYQ2000Theory of ComputationRegular and Context-free LanguagesMCQ · 1 mark
Let LL denote the languages generated by the grammar S→0S0∣00S \to 0S0 \mid 00. Which of the following is TRUE?
Official PYQ1999Theory of ComputationRegular and Context-free LanguagesMSQ · 1 mark
If L1L1 is context free language and L2L2 is a regular language which of the following is/are false?