Download PTU B.Tech 2021 Jan CSE 5th Sem 78321 Formal Language And Automata Theory Question Paper

Download PTU (Punjab Technical University) B.Tech (Bachelor of Technology) / BE (Bachelor of Engineering) 2021 January CSE 5th Sem 78321 Formal Language And Automata Theory Previous Question Paper

Roll No.
Total No. of Pages : 02
Total No. of Questions : 18
B.T ech. (CSE) (Sem.?5)
FORMAL LANGUAGE & AUTOMATA THEORY
Subject Code : BTCS-502-18
M.Code : 78321
Time : 3 Hrs. Max. Marks : 60
INST RUCT ION TO CANDIDAT ES :
1 .
SECT ION-A is COMPULSORY cons is ting of TEN questions carrying TWO marks
each.
2 .
SECT ION-B c ontains F IVE questions c arrying FIVE marks eac h and s tud ents
has to attempt any FOUR qu estio ns.
3 .
SECT ION-C contains THREE questions carrying T EN marks e ach and s tudents
has to attempt any TWO questions.
SECTION-A
Answer briefly :
1)
If A={a, b} and B={a, c}, Find A* U B*.
2)
State Kleene's Theorem.
3)
Find Regular Expression over {a,b} having set of all string containing exactly two a's.
4)
Differentiate between type1 and type2 grammar.
5)
State Arden's Theorem.
6)
Describe PDA.
7)
Differentiate between Injective and Surjective functions in a set.
8)
Write the steps needed for proving that a given set is not regular.
9)
Define Derivation Tree.
10) State Ambiguous grammar with example.
1 | M-78321
(S2)-115

---

SECTION-B
11) Describe pumping lemma for regular set with the help of an example.
12) Prove that string represented by following transition system is
(a + a(b + aa)*b)* a(b + aa)*a.
a
b
a
a
q1
q2
q3
b
a
13) Find a reduced grammar equivalent to the given grammar.
S AB
A a
B b
B C
E c
14) What are the different types of Grammars and Languages associated with it.
15) Discuss the Universality of Cellular Automata.
SECTION-C
16) Find a grammar in GNF equivalent to the grammar.
E E + T | T
T T * F | F
F (E) | a
17) Discuss the various representations of Turing Machine.
18) Design PDA for {wcwT | 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.
2 | M-78321
(S2)-115

---