Download GTU B.Tech 2020 Winter 5th Sem 3151605 Formal Language And Automata Theory Question Paper

Download GTU (Gujarat Technological University Ahmedabad) B.Tech/BE (Bachelor of Technology/ Bachelor of Engineering) 2020 Winter 5th Sem 3151605 Formal Language And Automata Theory Previous Question Paper

Seat No.: ________
Enrolment No.___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE- SEMESTER?V (NEW) EXAMINATION ? WINTER 2020
Subject Code:3151605 Date:27/01/2021
Subject Name:Formal Language and Automata Theory
Time:10:30 AM TO 12:30 PM Total Marks: 56
Instructions:
1. Attempt any FOUR questions out of EIGHT questions.

2. Make suitable assumptions wherever necessary.

3. Figures to the right indicate full marks.



MARKS
Q.1 (a) Define DFA, NFA and NFA-.
03

(b) Explain Addition, Multiplication, and Subtraction function for Primitive
04
Recursive Functions.

(c) Draw a Turing Machine(TM) to accept Even and odd Palindromes over
07
{a,b}.


Q.2 (a) Define the pumping lemma for context free language. Using Pumping
03
Lemma Prove that given Language is not CFL.
L={ 0i 1j 0k | k > i+j}.

(b) Design and draw a deterministic PDA accepting "Balanced strings of
04
Brackets" which are accepted by following CFG.
S SS | [ S ] | { S } |

(c) Convert the following NFA - into its equivalent DFA that accepts the
07
same language.
Q.3 (a) Write Regular Expression and Valid String for the following
03
a) The Language of all strings Containing both 11 and 010 as Substring.
b) The Language of all strings of length 6 or Less.

(b) Find context free grammar for the following language
04
L = {ai bj ck | i = j + k}

(c) Write a short note on Universal Turing Machine.
07




Q.4 (a) Consider following grammar:
03
S ASB |
A aAS | a
B SbS | A | bb
a) Eliminate useless symbols, if any.
b) Eliminate productions
1

---

(b) Draw F.A. and Transition Table for following.
04
c) The Language of all strings with 00 is not a Substring.
d) The Language of all strings end with 01.

(c) Write a Turing Machine to copy strings.
07
Q.5 (a) Define: Context-Free Grammars, Chomsky Normal Form and Pushdown
03
Automata.

(b) Calculate following:
04
1) * (q0, ) 2) * (q0, 0) 3) * (q0, 01) 4) * (q0, 010)

(c) Given the context-free grammar G, find a CFG G' in Chomsky Normal
07
Form generating L(G) ? {^}.
S AACD | ACD | AAC | CD | AC | C
A aAb | ab
C aC | a
D aDa | bDb | aa | bb



Q.6 (a) Draw F.A. and Transition Table for following.
03
(a+b)*baaa.

(b) Convert the given NFA to DFA
04
0, 1
1
0, 1
0, 1
q0
q1
q2
q
3

(c) Prove that the following CFG is Ambiguous.
07
S S + S | S * S | (S) | a
Write the unambiguous CFG for the above grammar. Draw parse tree for
string a+a*a
Q.7 (a) What is Initial Functions?
03

(b) Find a minimum-state FA for the following FA
04
2

---

(c) For the PDA, ({q0, q1}, {0, 1}, {0, 1, z0}, , q0, z0, ),
07
where is
(q0, , z0) = {(q1, )}
(q0, 0, z0) = {(q0, 0z0)}
(q0, 0, 0) = {(q0, 00)}
(q0, 1, 0) = {(q0, 10)}
(q0, 1, 1) = {(q0, 11)}
(q0, 0, 1) = {(q1, )}
(q1, 0, 1) = {(q1, )}
(q1, 0, 0) = {(q1, )}
(q1, , z0) = {(q1, )}
Obtain CFG accepted by the above PDA.



Q.8 (a) What is Primitive Recursive Functions?
03
(b) Define Pumping Lemma for Regular Language. Using Pumping Lemma
04
Prove that given Language is not regular Language.
L = { 0i 1j 0k | k > i + j}.
(c)
r
For the language L = { xcx / x {a,b}* } design a PDA(Push Down
07
Automata) and trace it for string "bacab"

*************
3

---