This download link is referred from the post: PTU B.Tech 5th Semester Last 10 Years 2011-2021 Previous Question Papers|| Punjab Technical University
Roll No. | | Total No. of Pages : 02
Total No. of Questions : 18
--- Content provided by FirstRanker.com ---
B.Tech. (CSE) (Sem.-5)
FORMAL LANGUAGE & AUTOMATA THEORY
Subject Code : BTCS-502-18
M.Code : 78321
Time : 3 Hrs. Max. Marks : 60
--- Content provided by FirstRanker.com ---
INSTRUCTION TO CANDIDATES :
- SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
- SECTION-B contains FIVE questions carrying FIVE marks each and students has to attempt any FOUR questions.
- SECTION-C contains THREE questions carrying TEN marks each and students has to attempt any TWO questions.
SECTION-A
--- Content provided by FirstRanker.com ---
Answer briefly :
- If A={a, b} and B={a, c}, Find A* U B*.
- State Kleene’s Theorem.
- Find Regular Expression over {a,b} having set of all string containing exactly two a’s.
- Differentiate between typel and type2 grammar.
- State Arden’s Theorem.
- Describe PDA.
- Differentiate between Injective and Surjective functions in a set.
- Write the steps needed for proving that a given set is not regular.
- Define Derivation Tree.
- State Ambiguous grammar with example.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
SECTION-B
- Describe pumping lemma for regular set with the help of an example.
- Prove that string represented by following transition system is (a+a(b +aa)*b)* a(b + aa)*a.
a b S T A - Find a reduced grammar equivalent to the given grammar.
S— AB A—a B—b B—C E—c - What are the different types of Grammars and Languages associated with it.
- Discuss the Universality of Cellular Automata.
--- Content provided by FirstRanker.com ---
SECTION-C
--- Content provided by FirstRanker.com ---
- Find a grammar in GNF equivalent to the grammar.
E—-E+T|T T=T*F|F F—(E)|a - Discuss the various representations of Turing Machine.
- Design PDA for {wew'|w = {a,b}*}.
NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any page of Answer Sheet will lead to UMC against the Student.
--- Content provided by FirstRanker.com ---
This download link is referred from the post: PTU B.Tech 5th Semester Last 10 Years 2011-2021 Previous Question Papers|| Punjab Technical University
--- Content provided by FirstRanker.com ---