J
N
T
U
W
O
R
L
D
Code No: R22055
II B. Tech II Semester, Supplementary Examinations, Dec 2012
FORMAL LANGUAGES AND AUTOMATA THEORY
(Computer Science and Engineering)
Time: 3 hours Max. Marks: 75
Answer any FIVE Questions
All Questions carry Equal Marks
~~~~~~~~~~~~~~~~~~~~~~~~
1. a) Construct a DFA that accepts an identifier of a C programming language.
b) Differentiate between NFA and DFA? (7M+8M)
2. a) Design a DFA that accepts the language over = {0, 1} of all strings that contain neither the
sub-string 00 nor the sub-string 11.
b) Construct a minimal state finite automaton to the following state diagram: (7M+8M)
3. a) Find the regular expression for the following finite automaton:
b) Show that the simplified regular expression recognized by the following DFA is the set of
all strings of as and bs that end with letter a. (7M+8M)
1 of 2
R10
SET - 1
www.jntuworld.com
www.jntuworld.com
www.jwjobs.net
J
N
T
U
W
O
R
L
D
Code No: R22055
4. a) Consider the following context free grammar:
Find the leftmost derivation, rightmost derivation, and parse tree for the string: a*(a+b00).
b) Write a context free grammar for the while statement in C language. (7M+8M)
5. a) Consider the following context free grammar, G:
Convert the G equivalent to G that has: no null productions, and no unit productions one after
the other.
b) Find the Greibach normal form of the following grammar:
(7M+8M)
6. Let M = ({q
0
, q
1
}, {a, b}, {X, Z
0
}, , q
0,
Z
0,
) be a push down automata (PDA) and is
defined by:
i) Find the language accepted by the PDA, M by empty store.
ii) Construct a context free grammar (CFG), G that accepts null store, N(M) (7M+8M)
7. a) Explain, briefly, about the different types of Turing Machines.
b) Design a Turing Machine (TM) that accepts the language, L = { 0
n
1
n
0
n
| n 1 } (7M+8M)
8. a) State and explain the undecidability of post correspondence problem
b) What do you meant by decidable and undecidable problems? Explain, in detail, P and NP
problems with examples. (8M+7M)
2 of 2
R10
SET - 1
www.jntuworld.com
www.jntuworld.com
www.jwjobs.net
J
N
T
U
W
O
R
L
D
Code No: R22055
II B. Tech II Semester, Supplementary Examinations, Dec 2012
FORMAL LANGUAGES AND AUTOMATA THEORY
(Computer Science and Engineering)
Time: 3 hours Max. Marks: 75
Answer any FIVE Questions
All Questions carry Equal Marks
~~~~~~~~~~~~~~~~~~~~~~~~
1. a) Give a finite state diagram that accepts all the floating-point numbers.
b) Design NFA to accept strings with as and bs such that the string end with ab (7M+8M)
2. a) Construct a minimal state Finite Automaton to the following state diagram:
b) Design a Moore machine and Mealy machine that accepts strings over = {0, 1} where,
if the input ends in 001, output a A; if the input ends in 100 , output a B; else output a C.
(7M+8M)
3. a) Construct an NFA and DFA for the Regular Expression: (0 + 1)*(00 + 11) 110.
b) Find the regular expression for the following finite automaton: (7M+8M)
4. a) Give the context free grammar that generates the set {0
n
1
n
n 1}
b) Consider the following context free grammar: E +EE *EE EE x y
Find the leftmost derivation, rightmost derivation, and parse tree for the string: + * x y x y
(8M+7M)
1 of 2
R10
SET - 2
www.jntuworld.com
www.jntuworld.com
www.jwjobs.net
J
N
T
U
W
O
R
L
D
Code No: R22055
5. a) Convert and reduce the following grammar such that there are no UNIT productions.
S AA
A B | BB
B abB | b | bb
b) Find the Greibach normal form of the following grammar: (7M+8M)
6. a) Construct the equivalent grammar for the PDA
{ } { } { } ( ) = , , , , , , 1 , 0 , ,
0 0 0 1 0
Z q Z R q q M and is given by
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( ) =
=
=
=
=
=
, , ,
, , 0 ,
, , 1 ,
, , 1 ,
, , 0 ,
, , 0 ,
1 0 1
1 1
1 1
1 0
0 0
0 0 0 0
q Z q
q R q
R q R q
R q R q
RR q R q
RZ q Z q
b) Design a PDA for a language ( ) { } s 1' of number < s 0' of number and 1 0 |
+ = w w L by
final state. (7M+8M)
7. a) Consider following transition table (States versus Tape symbols) of a Turing Machine, M:
b) Design a Turing Machine, M that accepts e set of strings with an equal number of 0s and
1s (7M+8M)
8. a) What is a universal Turing machine? Explain Turing reducibility.
b) Construct the LR(0) parser for the following grammar:
(7M+8M)
2 of 2
Find the computation sequence of the input string: 00B
R10
SET - 2
www.jntuworld.com
www.jntuworld.com
www.jwjobs.net
J
N
T
U
W
O
R
L
D
Code No: R22055
II B. Tech II Semester, Supplementary Examinations, Dec 2012
FORMAL LANGUAGES AND AUTOMATA THEORY
(Computer Science and Engineering)
Time: 3 hours Max. Marks: 75
Answer any FIVE Questions
All Questions carry Equal Marks
~~~~~~~~~~~~~~~~~~~~~~~~
1. a) Construct NFA in which double 1s followed by double 0s
b) Design FA that accepts set of all string with three consecutive 0s over = {0, 1}.
(7M+8M)
2. a) Design a DFA over = {0, 1} accepting all strings of even number of decimal numbers in
binary.
b) Construct a DFA equivalent to the following NFA diagram: (7M+8M)
3. a) When are two regular expressions said to be equivalent? Obtain the regular expression
represented by the regular set: {0, 1, 00, 01, 000, 001, 0000, 0001, }
b) Prove the following regular expression identities:
i) ( + 0) ( + 0)* = 0* ii) 1 + ( + 0) ( + 0)* 1 = 0*1
iii) + 1* (011)* (1* (011)*)* = (1 + 011)* (7M+8M)
4. a) For the following grammar give the leftmost and rightmost derivation for the string 00101.
S A | B
A 0A |
B 0B | 1B |
b) Construct the right linear grammar and left linear grammar for the language (0+1)*00(0+1)*
(7M+8M)
1 of 2
R10
SET - 3
www.jntuworld.com
www.jntuworld.com
www.jwjobs.net
J
N
T
U
W
O
R
L
D
Code No: R22055
5. a) Consider the following grammar G:
Find an equivalent grammar that has: no null productions, and no unit productions one after
the other.
b) Convert the given CFG into GNF
S CA
A a
C aB | b (7M+8M)
6. a) Design a PDA that accepts a string of a well formed parenthesis. Consider parenthesis is as
( ), [ ], { }.
b) Construct PDA equivalent to the following CFG
S 0A
A 0ABC | 1B | 0
B 1
C 2 (7M+8M)
7. a) Consider the following transition table (States versus Tape symbols) of a Turing Machine,
M:
If the initial Instantaneous Description (ID) is: q
1
( ( ) B, then what is the final ID?
b) Design Turing Machine over ={1} to accept the language L={1
m
/m is odd} (7M+8M)
8. a) What is a modified PCP? Explain with some suitable example.
b) Explain, in detail, NP Complete and NP hard problems with examples. (7M+8M)
2 of 2
R10
SET - 3
www.jntuworld.com
www.jntuworld.com
www.jwjobs.net
J
N
T
U
W
O
R
L
D
Code No: R22055
II B. Tech II Semester, Supplementary Examinations, Dec 2012
FORMAL LANGUAGES AND AUTOMATA THEORY
(Computer Science and Engineering)
Time: 3 hours Max. Marks: 75
Answer any FIVE Questions
All Questions carry Equal Marks
~~~~~~~~~~~~~~~~~~~~~~~~
1. a) Give a finite state diagram that accepts all the floating-point numbers.
b) Design NFA which accepts the language containing either 01 or 10 over ={0,1}.
(7M+8M)
2. a) Design a DFA that accepts the language over the alphabet, = {0, 1, 2} where the
decimal equivalent of the language is divisible by 3.
b) Design a Moore machine and Mealy machine that accepts strings over = {0, 1} where,
if the input ends in 001, output a A; if the input ends in 100 , output a B; else output a C.
(7M+8M)
3. a) Show that L={ 0
i
1
j
| gcd(i,j) =1} is not regular
b) Show that the following regular expression identities are equivalent: (7M+8M)
i) r
+
= r
*
r
+
ii) (r + s )
*
= ( r + s
*
)
*
4. a) Construct a context free grammar for generating the balanced parentheses, like ( ),
[ ], [( ) ( ) ], ( [ ] ), etc. and find the moves of the grammar to derive the string: ( [ ( ) ] ( ) )
b) Draw the parse tree for the production grammar: S (S) SS ~S i j, generating
the symbolic formula: (~ ~ i ( i ~ ~ j ) ). (7M+8M)
5. a) State and prove the pumping lemma for context free languages.
b) Give CFG for generating odd palindromes over the string {a,b} (7M+8M)
6. a) Design a PDA that accepts a string of a well formed parenthesis. Consider parenthesis is as
( ), [ ], { }.
b) Construct PDA equivalent to the following CFG
S 0A
A 0ABC | 1B | 0
B 1
C 2 (7M+8M)
7. a) State and prove the Turing Machine (TM) halting problem.
b) Design a Turing Machine, M that accepts a palindrome consisting of 0s and 1s of any
length. (7M+8M)
8. a) Describe in detail about halting problem of a Turing machine
b) Describe about modified Posts correspondence problem. (7M+8M)
1 of 1
R10
SET - 4
www.jntuworld.com
www.jntuworld.com
www.jwjobs.net
