GUJARAT TECHNOLOGICAL UNIVERSITY
BE- SEMESTER-V (NEW) EXAMINATION - WINTER 2020
--- Content provided by FirstRanker.com ---
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:
- Attempt any FOUR questions out of EIGHT questions.
- Make suitable assumptions wherever necessary.
- Figures to the right indicate full marks.
--- Content provided by FirstRanker.com ---
MARKS
Q.1 (a) Define DFA, NFA and NFA-?. 03
(b) Explain Addition, Multiplication, and Subtraction function for Primitive Recursive Functions. 04
--- Content provided by FirstRanker.com ---
(c) Draw a Turing Machine(TM) to accept Even and odd Palindromes over {a,b}. 07
Q.2 (a) Define the pumping lemma for context free language. Using Pumping Lemma Prove that given Language is not CFL. 03
L={ 0k 1j 0i | k > i+j}.
(b) Design and draw a deterministic PDA accepting “Balanced strings of Brackets” which are accepted by following CFG. 04
S ? SS | [S] | {S} | ?
--- Content provided by FirstRanker.com ---
(c) Convert the following NFA - ? into its equivalent DFA that accepts the same language. 07
a b
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.
--- Content provided by FirstRanker.com ---
(b) Find context free grammar for the following language 04
L={aibjck | i=j+k}
(c) Write a short note on Universal Turing Machine. 07
Q.4 (a) Consider following grammar: 03
S ? ASB | ?
--- Content provided by FirstRanker.com ---
A ? aAS | a
B ? SbS | ? | bb
a) Eliminate useless symbols, if any.
b) Eliminate ? productions
(b) Write Regular Expression and Valid String for the following 04
--- Content provided by FirstRanker.com ---
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 Automata. 03
(b) Calculate following: 04
--- Content provided by FirstRanker.com ---
1) d* (q0, ?) 2) d* (q0, 0) 3) d* (q0, 01) 4) d* (q0, 010)
(c) Given the context-free grammar G, find a CFG G’ in Chomsky Normal Form generating L(G) — {?}. 07
S ? AACD | ACD | AAC | CD | AC | C
A ? aAb | ab
C ? aC | a
--- Content provided by FirstRanker.com ---
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
(c) Prove that the following CFG is Ambiguous. 07
--- Content provided by FirstRanker.com ---
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
(c) Consider the following PDA, where 0 is 03
--- Content provided by FirstRanker.com ---
d(q0, ?, z0) = {(q1, ?)}
d(q0, 0, z0) = {(q0, 0z0)}
d(q0, 0, 0) = {(q0, 00)}
d(q0, 1, 0) = {(q0, 10)}
d(q0, 1, 1) = {(q0, 11)}
--- Content provided by FirstRanker.com ---
d(q0, 0, 1) = {(q1, ?)}
d(q1, 0, 1)={(q1, ?)}
d(q1, 0, 0)={(q1, ?)}
d(q1, ?,z0) = {(q1, ?)}
Obtain CFG accepted by the above PDA.
--- Content provided by FirstRanker.com ---
Q.8 (a) What is Primitive Recursive Functions? 03
(b) Define Pumping Lemma for Regular Language. Using Pumping Lemma Prove that given Language is not regular Language. 04
L={0k 1j 0i | k > i+j}.
(c) For the language L = { xxR / x ? {a,b}* } design a PDA(Push Down Automata) and trace it for string “bacab” 07
--- Content provided by FirstRanker.com ---
This download link is referred from the post: GTU B.Tech 2020 Winter Question Papers || Gujarat Technological University
--- Content provided by FirstRanker.com ---