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

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

Roll No.
Total No. of Pages : 02
Total No. of Questions : 18
B.T ech. (IT ) (Sem.?5)
FORMAL LANGUAGE & AUTOMATA THEORY
Subject Code : BTIT-501-18
M.Code : 78256
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)
Define Finite Automaton.
2)
What are various properties of transition function?
3)
Define grammar and language.
4)
Differentiate between left and right context in languages.
5)
Define yield in CFG.
6)
Define ambiguity in CFG.
7)
Define TM.
8)
Define the term acceptability in PDA.
9)
Give instantaneous description of Turing machine.
10) Differentiate between DFA and NDFA.
1 | M-78256
(S2)-25

---

SECTION-B
11) Write a note on canonical derivations.
12) Discuss the formal properties of LL(k) and LR(k) grammars.
13) Explain the concept of ambiguity with the help of example.
14) Construct a Moore machine equivalent to the Mealy machine M defined by following
table :
Next State
Present State
a = 0
a = 1
State
Output
State
Output
q1
q1
1
q2
0
q2
q4
1
q4
1
q3
q2
1
q3
1
q4
q3
0
q1
1
15) Find a reduced grammar equivalent to the given grammer.
S AB
Aa
Bb
BC
Ec
SECTION-C
16) Write a note on cellular automaton and rewriting systems.
17) Design PDA for {ambn |m > n}
18) Design Truing machine of{0n1n|n > = 1}
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-78256
(S2)-25

---