Semester-4 th
Branch-Computer Science & Engineering
Subject-Theory of Computation
i)
L={x ϵ {a,b}* : |x| a = odd and |x| b = even}
ii)
L={x ϵ {0,1}* : x does not contain more than
three 0’s}
2) If
language L is accepted by NFA then there exits an equivalent DFA that
accepts the same language.Explain with
example.
4) Define
Following
i) Finite State Machine
ii) Non Deterministic Finite Automata.
5) Construct a DFA over {0, 1 } that accept even number of 0's and odd number of 1's.
6) Design a
Mealy machine to determine
residue mod 3 for each binary string
treated as binary integer.
7) Construct
a DFA to accept the language over {0, 1} to accept a string 1100 or 1010 only.
8) Convert the NFA with ϵ -
transition to NFA without ϵ -
transition.
11) Design DFA's for the
languages over {0, 1) such that :
i) Every string WEL, W ends with 1 if it starts with 0 and ends 0 if it starts with L
ii) All strings ending in 0l or 10.
13) Design
a Moore machine to determine residue mod 3 for each binary string treated as binary integer.
14) Design
Moore machine for binary input sequence, if it ends in '101', output is A if it ends in '110' output is ‘B’ otherwise
'C'.
15) Construct
a deterministic finite automation equivalent to
M =({q0, q1, q2,q3},
{0,1}, δ,q0,{q3}) where δ is defined as -
13) Design
a DFA -
i) L={x
ϵ { a,b,c}* : |x| a = 0 mod 2
ii) L =
{x ϵ {0 , l}* / second symbol of x is 0
and fourth is 1 }
14) Give
the DFA accepting the following languages over alphabet {0, l}
i)
The set of all strings ending with
"00".
UNIT 2
1)
Construct the regular expression for the
following DFA.
2) Construct FA equivalent to Regular expression (0 + 1)* (00 + 11) (0 + 1)*.
3) Construct RLG and LLG.(Right linear grammar and Left linear grammar)
i) (0+1)*00 (0+1)*
ii) (0+1)*00 (0+1)
4) Show that the following language is not regular using pumping lemma
r = {ww R | w ϵ { a,b}}
5)
Construct a regular expression for the state
diagram described by:
6) Describe following sets by regular expressions:
i)Set of all strings of 0's and l's ending with '00' .
ii) Set of all strings of 0's and l's starting with 0 and ending with '1
7) Find the left linear and right linear grammar for (0+l)*00(0+1)*.
9) Construct the deterministic finite automation equivalent to the regular expression. (0+l)* (00+11) (0+1)
14)
Construct RLG & LLG for -
i)
(0+ l)*00(0+ 1)
ii)
L={0 n 1 m / n
> 0 & m > 1}
15)
Using pumping lemma. show that the following
languages are not regular i) L= {a p
/ p is prime}
ii) L= {ww | w ϵ { a,b}}
16) Let L = {a, b}, write Regular expression to
define language consisting of string w
such that -
i)
w contains ending with bb.
ii)
w
beginning with 0 and ending with b.
17) Construct NFA without € - equivalent to the following R. E.
i) 10+(0+11)0*l
ii) (0 + l)* (00 + l l) (0+1)*
UNIT 3
1)
What is CFG? Explain with suitable example?
2)
What is ambiguity in grammar? Explain with
suitable example?
3)
Construct Context Free Grammar for given
language
i) L={a n bm : n≠m}
ii)
L={ a n b m | 2n≤m ≤3n } for n,m>=0
4) Construct Context Free Grammar for given language
i) L={ a n b m : n≤ m+3 | n,m≥0 }
ii) L= {a n bn | n ≥ 0 }Ụ{ bn an| n ≥ 0}
5)
Construct Context Free Grammar for given
language
i) L={ a n b n c m dm | n≥1 ,m ≥ 1}
ii) L={an b m c m d
m | n ≥ 1 , m ≥ 1}
6)
Construct Context Free Grammar for given
language
i) L={ww R | w in (a+b)*}}
ii) L={ a n b n c m d m | n ≥ 0 , m ≥ 0}
7)
Design CFG for the regular language over {a,b}
that generates the set of
i) all string with exactly one a
ii) all string at least one a
8)
Design CFG for the regular language over {a,b}
that generates the set of
i) all string with at least 3 a’s.
ii) all string contain 3 consecutive a’s.
9)
Explain Derivation Tree and also explain RMD and
LMD with example?
10)
Explain Grammar simplification in details?
11)
Convert the following grammar into CNF
S→Aba, A→aab , B→Ac
12)
Convert the following grammar into CNF
S→AB, A→aA│ϵ , B→bB│ϵ
13)
Convert the following grammar into CNF
S→bA│aB, A→bAA│aS│a, B→aBB│bS│b
14)
Convert the following grammar into CNF
S→AB│aB, A→aab│ϵ , B→bbA
15)
Convert the following grammar into its
corresponding GNF
G= ({A1, A2, A3}, {a,b},P,A) Where productions
are
A1→A2A3
A2→A3A1│b
A3→A1A2 │a
16)
Convert the following grammar into its
corresponding GNF
S→ AA/a; A→ SS/b
17)
Convert the following grammar into GNF
i)S→AB, A→aA│ϵ , B→bB│ϵ
ii) S→ABb, A→aA│b
18)
Convert the following grammar into GNF S→aAS│a, A→SbA│SS│ba
UNIT 4
1)
Define Push down Automata with its tuples?
2)
Design a PDA for
L={WcW R │ W in (0+1)*} 3) Design a PDA for
L={W| n a( w)=n b( w)}
4)
Design a PDA for
L={ a n bn │ n≥0}
5)
Design a PDA for
L={ a n b 2 n │ n≥1}
6)
Design a PDA for
L={ a 3 b n c n │ n≥0}
L={ a n bm c n | m,n≥1 }
L={ am bm c n | m,n≥1}
L={a2 n cb n | n, m ≥ 1}
7) Design a NPDA for
L={WW R │ W in (0+1)*}
8)
Construct PDA equivalent to following grammar
S→aaA A→aS/bS/a
S→aSbb/aab
9)
Using pumping lemma, Show that
L={a i bj ci d j | i,j ≥ 1} is not CFL
L={a P | P is Prime} is not CFL
L={ a n bj : n=j 2 } is not CFL
L={a i b j c k | i<j<k } is not CFL
10)
Explain Enumeration of properties of CFL
11)
Explain Context Sensitive Language with example
12)
Generate a Context Sensitive Grammar for
L= {a n b n cn |n>=1} and Verify w=aaabbbccc
13)
Define Linear Bounded Automata?
14) Find the grammar generating the set accepted by LBA whose transition table is as follows: q1: Initial State q4: Final State
15)
Show
that L={W| n a( w)!=n b (
w)} is
deterministic context free language ( DCFL).
Give DPDA for it.
16) Show that there exit some LBA M, for every context sensitive language L such that L=L(M).
17) Explain closure properties of DCFL?
UNIT 5
1. Consider the Turing machine M described by the transition table given below. Describe the processing of
i) 011.
Using IDs. Which of the above strings are
accepted by M2
2.
Design a Turing machine over {0, 1} to accept
the language L={0m 1 m | m>0}
3.
Design
a Turing machine
which can compute
a concatenation function
over Σ={1} . If a pair of words (w1, w2) is the input, the output has to
be wlw2.
4. Design
a Turing machine
to compute m-n
where m and
n are positive integers and m> n.
5. Design à Turing machine for L={ww r
| w 
(a, b)*}.
6. Design à Turing machine for L={ww | w 
(0, 1)*}.
7. Explain
a TM with
two way infinite
tape and write
a relation with
one way infinite tape.
11. Design a Turing machine for L (0 n 1 n | n>=1) and verity the string i)0011
ii)011.
12.
Explain in brief:
i)Multi Track TM
ii) Multi Tape TM
iii) Multidimensional TM
13.
Design
a Turing machine
that computes the
proper subtraction of two unary
numbers
Proper subtraction (A, B) =A-B if A>B
= 0
if A<B
14.
Write a note on Church's hypothesis and Counter
Machines.
15.
Design a TM that computes the function
f(m,n)=m+n.
16.
Design a Turing machine to compute the
multiplication of two numbers
17.
Give recursive definitions of :(i)n+m (ii)n-m
(iii)nm.
18.
Design a Turing machine for f(x, y) = x-y if x
>= y
= 0 if x < y
UNIT-VI
1. Show that the function f(x, y) = x+y is
primitive recursive.
2. Explain PCP and MPCP Describe whether following
(A, B) parts have a solution are
not. If yes
give a solution.
If no, why?
A=(ab, b, b}
B={abb, ba, bb}
3. Explain
Universal Turing machine
with example? What
are the modification
made to the basic model of Turing machine.
4.
Show that the following function is primitive
recursive:
F(y)= 4y
if y is perfect square
= 4y+1
otherwise
5.
Prove the following
i) The complement of a recursive language is recursive. ii) The union of two recursive language is recursive
6. Describe in brief what is halting problem of TM.
7. Decide whether the following pair (A, B) have PCP solution or not? If yes give a solution if no why?
i) A ={1, 10111, 10} B={111, 10, 0}
ii) A ={10, 011,101} B={101, 11, 011}
8.
Ackerman's function defined by
A(0, y) = y+1
A(x+1,0)=A(x, 1)
A(x+1, y+1)=A(x, A(x+1, y)) Find A(1,1), A(1,2), A(2.1)
9. What is MPCP? Determine whether the following ( A B) Pairs have a MPCP solution or not? If yes, give a solution if no why?
i) A=(b, bab 3 , ba); B=(b 3 ,ba,a) ii) A=(1 2 ,10 2 ,1 3 ) ; B=(1 3 ,0²1,1²)
10.
Show that the following functions are recursive.
i)
n+m ii) nm
11.
Explain the
properties of Recursive and Recursively
enumerable languages in detail.
12. Prove that for any total recursive σ there exists an x 0 such that fx 0( x)=fσ (x 0) for all x
13) Let Σ={0,1} let X and Y be lists of three strings each defined as follows:
|
|
List
X |
List
Y |
|
i |
w i |
xi |
|
1 |
1 |
111 |
|
2 |
10111 |
10 |
|
3 |
10 |
0 |
