Date: 25 Apr 2023 Regd. No.
Sub Code: 20CS5T01 MIC20
B. Tech V Semester Supplementary Examinations, April-2023
FORMAL LANGUAGES & AUTOMATA THEORY
(CSE, IT)
Time: 3 hours Max Marks: 70M
------------------------------------------------------------------------------------------------------
Note: 1. Answer any five Questions with ‘either or choice’. One Question from Each Unit.
2. All Questions carry Equal Marks. 5 X 14 = 70M
UNIT - I
a) Design an NFA for the set of all strings over alphabet {0,1,2,3,4,5,6,7,8,9} such that 7M
1.
the final digit has never appeared before.
b) Construct DFA for the given NFA where q0 is an initial state and q3 is a final state 7M
0 1
q0 q0,q1 q0
q1 Ф q2
q2 q3 Ф
q3 q3 q3
(OR)
2. a) Construct NFA without ε for a given NFA with ε where q0 and q2 are the initial and 7M
final states respectively.
a b c ε
q0 q0 Ф Ф q1
q1 Ф q1 Ф q2
q2 Ф Ф q2 Ф
b) Design an NFA for the set of all strings containing either 00 or 11 7M
UNIT - II
3. a) Minimize the finite automaton given below. 7M
b) If the regular set A is represented by A = (01 + 1)* and the regular set 'B' is represented by 7M
B=((01)*1*)* . Find the relationship between them
(OR)
4. a) Show that the intersection of two regular sets is regular 7M
b) Let G=({S,A1,A2},{a,b},P,S) where p consists of SaA1A2a, A1baA1A2b, A2A1ab, 7M
aA1baa, bA2babab. Test whether w=baabbabaaabbaba is in L(G)
UNIT – III
5. a) If G =({S,A1},{0,1,2},P,S) where P consists of S0SA12,S012,2A1A12, 1A111. 7M
Prove that L(G)={0n1n2n / n>=1}
b) Construct a grammar for a language L={w/w has equal number of o’s and 1’s} where 7M
Σ={0,1}
(OR)
6. a) Prove that the grammar G with productions S a/ aAb /abSb AaAAb / bS is 7M
ambiguous. Show the derivation tress for the string considered.
b) Determine a CFG for the language L={anbmambn, where n,m >=1}. 7M
UNIT – IV
7. a) Give an example of a language which is accepted by NDPDA but not by DPDA and 7M
and write the NDPDA moves of it.
b) Show that the language L= {0n1m / m= 2n,m, n ≥ 0} is deterministic CFL by Constructing 7M
PDA moves.
Page 1 of 1
(OR)
8. a) Design PDA for the following language L = {2m 1m / m ≥ 1} 7M
b) Construct PDA for the following language L = {an b2n / n ≥ 1} 7M
UNIT – V
9. a) Construct a TM to accept L = {wcwr / w Є {0, 1)*} 7M
b) Design a TM over Σ={a,b} to accept the language L={ wCw/wε{a,b}+ } 7M
(OR)
10. a) Design a TM to recognize the language L={ 0n1n0n/n>=1} 7M
b) Differentiate between different types of Turing Machine in your own words. 7M
***End of Question Paper***
Page 1 of 1
