How are context-free grammars (CFG) tested in GATE Theory of Computation?

GATE tests CFG by asking you to identify the language generated by a given grammar, determine whether a grammar is ambiguous, convert a CFG to Chomsky Normal Form (CNF) or Greibach Normal Form (GNF), and find whether a given string belongs to the language of a CFG.

What is the difference between PDA and DFA in GATE TOC?

A DFA recognizes regular languages using only finite state. A PDA recognizes context-free languages by adding an unbounded stack to a finite automaton. GATE tests PDA construction for languages like {a^n b^n}, acceptance by final state vs empty stack, and whether a language requires a PDA or a DFA suffices.

What is Chomsky Normal Form and why is it important for GATE?

CNF is a normalized form of CFG where every production is either A → BC (two non-terminals) or A → a (single terminal). GATE tests CNF conversion steps (eliminating epsilon productions, unit productions, useless symbols) and uses CNF as the basis for the CYK parsing algorithm.

How is the pumping lemma for context-free languages used in GATE?

The CFL pumping lemma states that for any CFL L, strings longer than pumping length p can be split as uvxyz where |vxy| ≤ p, |vy| ≥ 1, and uv^i xy^i z ∈ L for all i ≥ 0. GATE asks you to prove languages like {a^n b^n c^n | n ≥ 0} are not context-free.

CS/IT Gate Subject

Aptitude and Reasoning
Engineering Mathematics
C Programming
Data Structure
Design Algorithm Analysis
Operating System
Computer Network
Digital Logic Design
Compiler Design
Database Management System
Theory of Computation

Automata GATE previous year questions with answer

1 2 3 4 5

Ques 27 Gate 2019

For Σ = {a, b}, let us consider the regular language

L = {x ∣ x = a^{2+ 3k} or x = b^{10 + 12k}, k ≥ 0}

Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

(Regular Language) is the correct answer.

Ques 28 Gate 2018

Consider the following languages:

I. {a^mbⁿc^pd^q ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {a^mbⁿc^pd^q ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {a^mbⁿc^pd^q ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {a^mbⁿc^pd^q ∣ mn = p + q, where m, n, p, q ≥ 0}

Which of the above languages are context-free?

I and IV only

I and II only

II and III only

II and IV only

(Context Free Grammar) is the correct answer.

Ques 29 Gate 2017 Set-2

The minimum possible number of states of a deterministic finite automaton that accepts a regular language L = {w₁aw₂ | w₁, w₂ ∈{a,b}* , |w₁| = 2, w₂>=3} is_______

(a) is the correct answer.

Ques 30 Gate 2017 Set-2

Identity the language generated by following grammar where S is the start variable.

S --> XY
X --> aX | a
Y --> aYb | ∈

{a^m bⁿ| m>=n, n>0 }

{a^m bⁿ| m>=n, n>=0 }

{a^m bⁿ | m>n, n>=0 }

{a^m bⁿ| m>n, n>0 }

(G) is the correct answer.

Given:
Grammar with start symbol S:
S → XY
X → aX | a
Y → aYb | ∈
To find:
The language generated by this grammar.
Solution:
First, let me look at the variable X.
X produces either a or calls itself with an a, with no option to produce ∈.
So, X generates at least one a:
L(X) = {a^k | k ≥ 1}
Now let me check the variable Y.
Y adds an a on the left and a b on the right, or it terminates with ∈.
So, Y generates an equal number of a's and b's, including the empty string:
L(Y) = {aⁿ bⁿ | n ≥ 0}
Now, combining them through S → XY:
Any string derived from S has the form w = a^k aⁿ bⁿ = a^k+n bⁿ.
Let m be the total number of a's, so m = k + n.
Since k ≥ 1, we have m = k + n ≥ 1 + n, which means m > n.
Also, since Y can derive ∈, n can be 0, so n ≥ 0.
Putting these conditions together gives:
L(S) = {a^m bⁿ | m > n, n ≥ 0}
This matches option C directly.
Answer: (C) {a^m bⁿ | m>n, n>=0 }

Ques 31 Gate 2017 Set-2

Let L1 and L2 be any context-free language and R be any regular language. Then, which of the following is correct ?

I. L1 ∪ L2 is context-free.
II. L1' is context-free.
III. L1-R is context-free.
IV. L1 ∩ L2 context-free.

I only

I and III only

II and IV only

I, II and IV only

(R) is the correct answer.

Given:
L₁ and L₂ are context-free languages (CFLs).
R is a regular language.
To find:
Which of the given statements are correct.
Solution:
Let me check statement I first.
Statement I says: L₁ ∪ L₂ is context-free.
I know that context-free languages are closed under union, so this statement is true.
Now let me check statement II.
Statement II says: L₁' is context-free.
CFLs are not closed under complementation, so L₁' is not necessarily context-free.
Thus, statement II is false.
Now checking statement III.
Statement III says: L₁ - R is context-free.
I can rewrite set difference as: L₁ - R = L₁ ∩ R'
Since regular languages are closed under complement, R' is also a regular language.
Also, the intersection of a CFL and a regular language is always a CFL.
So, L₁ ∩ R' is context-free, which means statement III is true.
Now checking statement IV.
Statement IV says: L₁ ∩ L₂ is context-free.
CFLs are not closed under intersection, so this is not necessarily context-free.
Thus, statement IV is false.
So only statements I and III are correct.
Answer: (B) I and III only

Ques 32 Gate 2017 Set-1

Consider the following grammar:

where relop is a relational operate (e.g < >, ….), ε refers to the empty statement, and if ,then, else are terminals. Consider a program P following the above grammar containing ten if terminals. The number of control flows paths in P is ____________. For example, the program

if e1 then
e2
else
e3

has 2 control flow paths, e1 -> e2 and e1 -> e3

(a) is the correct answer.

Ques 33 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 a deterministic finite-state automaton (DFA) accepting L is ______.

(4) is the correct answer.

Ques 34 Gate 2017 Set-1

Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B* .We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denotes the language {x#f(x)|x∈A*}. Which of the following statements is true?

f if computable if and only if Lf is recursive.

f if computable if and only if Lf is recursive enumerable.

if f is computable then Lf is recursive, but not conversely.

if f is computable then Lf is recursively enumerable, but not conversely.

(a) is the correct answer.

Ques 35 Gate 2017 Set-1

Consider the following languages over the alphabet ∑= {a,b,c}.
Let L1 ={aⁿbⁿc^m | m, n >= 0 } and
L2 = {a^mbⁿcⁿ| m, n >= 0}.

Which of the following are context-free languages ?
I. L₁ ∪ L₂
II. L₁ ∩ L₂

I only

II only

I and II

Neither I nor II

(a) is the correct answer.

Ques 36 Gate 2017 Set-1

If G is grammar with productions

S → SaS | aSb | bSa | SS | ∈

where S is the start variable, then which one of the following is not generated by G?

abab

aaab

abbaa

babba

(CFG) is the correct answer.

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Subject

Automata GATE previous year questions with answer

Question Options

Sign in to ExamPrev