Download - Dhanalakshmi Srinivasan Institute of Research and

DHANALAKSHMI SRINIVASAN INSTITUTE OF RESEARCH AND TECHNOLOGY
SIRUVACHUR, PERAMBALUR-621113
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Third Year CSE( Sem:V)
CS2303- THEORY OF COMPUTATION
PART B-16 MARKS
UNIT-I AUTOMATA
1.If L is accepted by an NFA with ε-transition then show that L is accepted by an
NFA without ε-transition.
Hint:
1.Write the NFA regular expression.
2. Prove the Relation.
2 . Construct a DFA equivalent to the NFA.
M=({p,q,r},{0,1}, δ,p,{q,s})
Where δis defined in the following table.
δ
p
q
r
s
0
{q,s}
{r}
{s}
-
1
{q}
{q,r}
{p}
{p}
Hint:
1.Draw the NFA diagram.
2.Write the tuples of NFA.
3.Find the States.
4.Draw the equivalent DFA diagram
n
n
3. Show that the set L={a b /n>=1} is not a regular. (6) b)Construct a DFA equivalent to the
NFA given below: (10)
0
1
{p,q}
P
p
R
q
r
r
s
S
s
s
Hint:
1.Draw the NFA diagram.
2.Write the tuples of NFA.
3.Find the States.
4.Draw the equivalent DFA diagram
n
n
4.Check whether the language L=(0 1 /n>=1) is regular or not? Justify your answer.
Hint:
1.Assume the regular function.
2.Find the value of W.
3.Prove the Condition.
4.Apply the value k=0,1,2.
5.By the values of xykz it is identified the function is regular or not.
4. Define NFA with ε-transition. Prove that if L is accepted by an NFA with εtransition then L is also accepted by a NFA without ε-transition.
Hint:
NFA- ε theorem.
5. Construct DFA equivalent to the NFA given below:
Hint:
1.Draw the NFA diagram.
2.Write the tuples of NFA.
3.Find the States.
4.Draw the equivalent DFA diagram
6. Prove that a language L is accepted by some ε–NFA if and only if L is accepted by
some DFA.
Hint: NFA Language theorem.
7. Consider the following ε–NFA.Compute the ε–closure of each state and find it’s
equivalent DFA.
ε
A
b
C
Hint:
1.Draw the NFA diagram.
p
{q}
{p}
Ф
Ф
q
{r}
ф
{q}
Ф
*r
Ф
ф
ф
{r}
2.Write the tuples of NFA.
3.Find the Existing or new States
4.Draw the equivalent DFA diagram
8. Convert the following NFA to it’s equivalent DFA
0
1
p
{p,q}
{p}
q
{r}
{r}
r
{s}
ф
*s
{s}
{s}
Hint:
1.Draw the NFA diagram.
2.Write the tuples of NFA.
3.Find the Existing or new States
4.Draw the equivalent DFA diagram
UNIT-II REGULAR EXPRESSIONS AND LANGUAGES
1.Construct an NFA equivalent to (0+1)*(00+11)
Hint:
1.Find the function for each value.
2.Identify the cases.
3.Draw the diagram based on the function.
2.Construct a Regular expression corresponding to the state diagram given in the
following figure.
Hint:
1.Find the Appropriate Cases for the Given function.
2.Eliminate the states one by one.
3.Write the final R value.
i
i
3. Show that the set E={0 1 |i>=1} is not Regular.
Hint:
1.Assume the regular function.
2.Find the value of W.
3.Prove the Condition.
4.Apply the value k=0,1,2.
5.By the values of xykz it is identified the function is regular or not.
4. Construct an NFA equivalent to the regular expression (0+1)*(00+11)(0+1)*.
Hint:
1.Find the function for each value.
2.Identify the cases.
3.Draw the diagram based on the function.
5.Obtain the regular expression denoting the language accepted by the following DFA by
using the formula Rij
k
Hint:
1.Write the General formula for the conversion of Finite automata to regular expression.
2. Find the value of i,j,k .
3.Find the value by applying k=0,1
4.Apply the values in the formul and find the final regular expression R.
2
6. Define a Regular set using pumping lemma Show that the language L={0i / i is an
integer,i>=1} is not regular
Hint:
1.Assume the regular function.
2.Find the value of Wand states as n=2.
3.Prove the Condition.
4.Apply the value k=0,1,2.
5.By the values of xykz it is identified the function is regular or not
7.Find whether the following languages are regular or not.
R
(i) L={w ε{a,b}|w=w }.
n
m
(ii) L={0 1 2
k
n+m
2
,n,m>=1}
(iii) L={1 |k=n ,n>=1} . (4)
(iv) L1/L2={x | for some y εL2,xy εL1},where L1 and L2 are any two languages and
L1/L2 is the quotient of L1 and L2.
Hint:
1.Assume the regular function.
2.Find the value of Wand states as n=2.
3.Prove the Condition.
4.Apply the value k=0,1,2.
5.By the values of xykz it is identified the function is regular or not
UNIT-III CONTEXT FREE GRAMMARS AND LANGUAGES
1. Let G be a CFG and let a=>w in G. Then show that there is a leftmost
derivation of w.
Hint: Theorem of CFG.
2. Let G be a grammar s->OB/1A, A->O/OS/1AA, B->1/1S/OBB. For the string
find its leftmost derivation and derivation tree.
Hint:
1.Find the left most derivations.
2.Write the Right most derivations for the tree.
3.Construct the accurate derivation tree.
3. If G is the grammar S->Sbs/a, Show that G is ambiguous.
Hint:
1.Find the left most derivations.
2.Write the Right most derivations for the tree.
3.Construct the accurate derivation tree.
4.Show that E->E+E/E*E/(E)/id is ambiguous.
Hint:
1.Find the First left most derivations.
2.Find the Second left most derivations.
3.Construct Parse tree for the left most derivations and Right most derivations.
5.Construct a Context free grammar G which accepts N(M), where M=({q0,
q1},{a,b},{z0,z},δ,q0,z0,Φ) and where δ is given by
δ(q0,b,z0)={(q0,zz0)}
δ(q0, ε,z0)={(q0, ε)}
δ(q0,b,z)={(q0,zz)}
δ(q0,a,z)={(q1,z)}
δ(q1,b,z)={(q1, ε)}
δ(q1,a,z0)={(q0,z0)}
00110101
Hint:
1. Construct a Context free grammar.
2. Apply the formula.
6. If L is Context free language then prove that there exists PDA M such that
L=N(M).
Hint:
Context free language Theorem and its steps.
n m n
7. Construct a PDA accepting {a b a /m,n>=1} by empty stack. Also construct the
corresponding context-free grammar accepting the same set.
Hint:
1.Write the Appropriate CFG.
2.Find the Values .
8. Find the left most and right most derivation corresponding to the tree.
Hint:
1.Find the First left most derivations.
2.Find the Second left most derivations.
UNIT-IV PROPERTIES OF CONTEXTFREE LANGUAGES
1.Convert to Greibach Normal Form the grammar G=({A1, A2,
A3},{a,b},P,A1 ) where P consists of the following. A1 ->A2 A3, A2 >A3 A1 /b,A3 ->A1 A2 /a.
Hint:
1.
2.
3.
4.
Write the grammar definition.
Find the form of a grammar.
Replace the variables.
Construct the GNF.
2.Convert the grammar S->AB, A->BS/b, B->SA/a into Greibach NormalForm
Hint:
1.
2.
3.
4.
.
Write the grammar definition.
Find the form of a grammar.
Replace the variables.
Construct the GNF.
3.Construct a equivalent grammar G in CNF for the grammar G1 where G1
=({S,A,B},{a,b},{S->bA/aB,A->bAA/aS/a, B->aBB/bS/b},S) .
Hint:
1.
2.
3.
4.
Write the grammar definition.
Find the form of a grammar.
Replace the variables.
Construct the GNF.
4.Begin with the grammar
S->0A0/1B1/BBA->CB->S/AC->S/ ε
and simplify using the safe order Eliminate ε-Productions Eliminate unit production
Eliminate useless symbols Put the (resultant) grammar in Chomsky Normal Form .
Hint:
1. write down the start variable
2. find a rule and replace
3.find a rule and replace
4.find a rule and replace
5.find a rule and replace.
5.Explain the Construction of an equivalent grammar in CNF for thegrammar
G=({S,A,B}{a,b},P,S)
where P={S->bA|aB, A->bAA|aS|a, B->aBB|bS|b} (10)
Hint:
1. write down the start variable
2. find a rule and replace
3.find a rule and replace
4.find a rule and replace
5.find a rule and replace.
UNIT-V UNDECIDABILITY
1.Define the language Ld and show that Ld is not recursively enumerable language.
Hint:
Recursively enumerable Languages
M is said to generate a string w if and only if at some point M writes
w# on the output tape. G(M) = {w | M generates w}
Note: M need not generate strings in order. It is also possible that M
generates some strings many times!
Definition: L is recursively enumerable (r.e.) iff there is a TM M such
that L = G(M).
2.Explain the Halting problem. Is it decidable or undecidable problem .
Hint:
In computability theory, the halting problem is the problem of determining, from a
description of an arbitrary computer program and an input, whether the program will finish
running or continue to run forever.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible
program-input pairs cannot exist. A key part of the proof was a mathematical definition of a
computer and program, which became known as a Turing machine; the halting problem
is undecidable over Turing machines. It is one of the first examples of a decision problem.
3.Define Universal language Lu.Show that Lu is recursively enumerable but
not recursive.
Hint:
The Universal Language Lu is a set of binary strings which can be
modeled by a turning machine.
4.Obtain the code for the TM M=({q1,q2,q3},{0,1},{0,1,B},
δ,q1,B,{q2}) With the moves δ(q1,1)=(q3,0,R) δ(q3,0)=(q1,1,R)
δ(q3,1)=(q2,0,R) δ(q3,B)=(q3,1,L) δ(q3,B)=(q3,1,L)
Hint:
1. Identify the mapping Function.
2. Note the codes for function.
3. The code for Tm can be written.
5. Define Ld and show that Ld is not recursively enumerable.
Recursively enumerable Languages
M is said to generate a string w if and only if at some point M writes
w# on the output tape. G(M) = {w | M generates w}
Note: M need not generate strings in order. It is also possible that M
generates some strings many times!
Definition: L is recursively enumerable (r.e.) iff there is a TM M such
that L = G(M).
6.Define the universal language and show that it is recursively enumerable
but not recursive.
Hint:
A language is recursively enumerable if some Turing machine accepts it
Let be a L recursively enumerable language
and the Turing Machine that accepts it M w∈ L w
if then halts in a final state M if w∉ L then M halts in a non-final state
or loops forever.
7.State and Prove Rice’s Theorem for recursive index sets.
Hint:
• It is more complicated to find out
whether L is or is not recursively enumerable (rec. enum.)
• Rice has a theorem: L is rec. enum. if and only if satisfies 3 conditions.

Download Report