cs402 mid term current paper subjective fall 4 December 2011

Question#1 Consider the CFG ( 5marks)
S--> bS | aX | ^
X--> aX | bY | ^
Y--> aX | ^

Derive the following string from CFG. Show all steps
baabab
ababaab

Question#2 Construct corresponding CFG for the given language (5 mark)
(1) All words of even length but not multiple of 3.
(2) Palindrome (both even and odd palindrome).

Question#3 Write the CFG for the following RE
(a+b)* aa (a+b)*
( 5Marks)

Question-4.What does the following arbitary summary table shows (3 Marks)

From
Where
READ 9

To
Where
READ3

READ
What
b

POP
What
b

Push
What
abb

ROW
number
11

Question #5.Is the following CFG ambiguous? How can you remove the ambiguity?
S→aS│bS│aaS│ ^ ( 3marks)
=
ab
{,}
∑

Question# 6. If L1, L2, L3 are any three finite languages on
∩∪∩≠∅
LLLL
(12)(13)
(3marks)

Question#7.Construct RE for the language having words of even length over ∑= {a.b} (2
Mark)

Question#8.A Push down Automata consists of and input TAPE with ----------many
location in one direction. (Marks 2)

Question# 9. Write alternative form of this production (2 Marks)
→→→∧
SaSSbSS
,,

, when will be the

Question 10. What is the first step when you want to write RE corresponding to TG
(2Marks??)