BSC CSIT Semester 4 – Theory of Computation () Questions & Answers | Past TU Exam Papers

Question 1

Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each.

Marks: 5

Year: 2076 Final TU

Definition of CNF: A Context-Free Grammar (CFG) is said to be in Chomsky Normal Form (CNF) if all production rules are of the form: 1. A → BC (where A, B, C ∈ V and B, C are non-terminals) 2. A → a (w

Question 2

Explain about the Chomsky’s Hierarchy about the language and programs.

Marks: 5

Year: 2078 Final TU

--- OR ---

Question 3

Construct the following grammer into Chomsky Normal Form. S → abSb | a | aAb A → bS | aAAb | ε

Marks: 5

Year: 2078 Final TU

Conversion to Chomsky Normal Form (CNF) Original Grammar: S → abSb | a | aAb A → bS | aAAb | ε Step 1: Eliminate ε-productions Find Nullable Variables: - A → ε, so A is nullable - Check other pro

Question 4

Given the following expression grammar for simple arithematic expression with operator + and . E→ E+T | T T → T+F | F F → (E) | a Remove the left recursion from this grammar then simplify and convert

Marks: 10

Year: 2079 Final TU

Note / Assumption: The given grammar mentions operators + and but the second production was written T → T+F | F. I assume this is a typo and the intended production is the usual T → T F | F (i.e.

Question 5

Define the term: Parse Tree, left-most and right-most derivation, sentential form and ambiguity with example.

Marks: 5

Year: 2079 Final TU

1. Parse Tree A parse tree is a tree representation that shows how a string (sentence) is derived from a grammar using its production rules. - The root is the start symbol. - Internal nodes are no

Question 6

Define regular grammar. Also explain the method of converting right linear grammar into equivalent finite automata.

Marks: 5

Year: 2079 Final TU

1. Definition of Regular Grammar A Regular Grammar (RG) is a type of grammar used to generate regular languages. It has production rules in a specific restricted form. A grammar is called Regular if

Question 7

Define context free grammar with an example. Explain with example, how context free grammar is converted to Chomsky Normal Form.

Marks: 10

Year: 2080 Final TU

Context Free Grammar (CFG) and Conversion to Chomsky Normal Form (CNF) Definition of Context Free Grammar (CFG) A Context Free Grammar (CFG) is a formal grammar that generates Context Free Language

Question 8

What is the meaning of the term “Context Free” in context free grammar? Justify with a suitable example. What is the need of a parse tree?

Marks: 5

Year: 2080 Final TU

Meaning of the term “Context Free” A grammar is called Context Free because each production rule has a single non-terminal on the left-hand side, and that non-terminal can be replaced independently of

Question 9

Define CFG. Construct a CFG that generates the language of all palindromes over {a,b} that do not contain the substring aa. Show the leftmost derevation and construct the equivalent parse tree for str

Marks: 10

Year: 2080 Final TU

1. Definition of Context Free Grammar (brief) A Context Free Grammar (CFG) is a 4-tuple \(G=(V,T,P,S)\) where: - \(V\) is a finite set of nonterminals, - \(T\) is a finite set of terminals, - \(P\) is

Question 10

Prove that the language \(L=\{\,a^n b^n c^n \mid n \ge 0\,\}\) is not a context free grammar.

Marks: 5

Year: 2080 Final TU

Claim: \(L = \{a^n b^n c^n \mid n \ge 0\}\) is not context-free. Proof (using pumping lemma for CFLs): Assume \(L\) is context-free. Let \(p\) be the pumping length. Consider the string \[ s = a