DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Faculty Name : Dr Geetha C Megharaj
Subject : Theory of Computation
Subject Code :BCS503
Semester : V CSE
SOLUTION TO MODEL QUESTION PAPER -1
Q. Question & Solution Year
No.
1 a) 5
Obtain a DFA to accept strings of a’s and b’s having odd number of a’s and even number of b’s Marks
δ a b
→ 00 10 01
01 11 00
* 10 00 11
11 01 10
Draw a DFA to accept decimal strings divisible by 3
b) L= {3,6,9,12,15,18,21….. }
Solution : possible remainders : 0,1,2,
6
states = {Q0,Q1,Q2}
δ(Qi, d) = Qj Marks
J=(10*i + d) mod 3
δ 0 1 2
→* Q0 (10*0 + 0) mod 3 = (10*0 + 1) mod 3 (10*0 + 2) mod 3
0 =Q0 = 1 =Q1 = 1 =Q2
Q1 (10*1 + 0) mod 3 = (10*1 + 1) mod 3 (10*1 + 2) mod 3
1 =Q1 = 2 =Q2 = 0 =Q0
Q2 (10*2 + 0) mod 3 = (10*2 + 1) mod 3 (10*2 + 2) mod 3
1 =Q2 = 0 =Q0 = 1 =Q1
TRANSITION TABLE
δ 0 1 2
→ * Q0 Q0 Q1 Q2
Q1 Q1 Q2 Q0
Q2 Q2 Q0 Q1
TRANSITION DIAGRAM
Define the following terms with examples. 1)Alphabet 2) Power of an alphabet 3)) Languages
c)
Solution :
1)Alphabet
Defn: An alphabet is a non-empty, finite set of characters/symbols
Use Σ to denote an alphabet set
Examples 9
Σ = { a, b }
Marks
Σ = { 0, 1, 2 }
2) Power of an alphabet
Power set of an alphabet is set of strings formed by concatenating the characters of alphabet any
number of times.
Σ = { a, b }
Σ0={ε}
Σ 1 = { a, b}
Σ 2 = { aa, bb,ab,ba} …….
Σ * = Σ 0 U Σ 1 U-----------U Σ n
Is set of strings of any length
3) String
Definition: A string is a finite sequence, possibly empty, of characters drawn from some
alphabet Σ.
ε is the empty string
Σ * is the set of all possible strings over an alphabet Σ.
Examples of strings:
Σ = {a, b}
Strings derived from Σ are…..
….. ε , a, b, aa, ab, ba, bb, aaa, aab, aba, ..
4) String concatenation
Definition– to join two or more strings. Operator - s||t, or nothing i.e. st
x = good, y = student
Concatenation operation x||y or xy
xy = goodstudent
5) Language
Defn: A language is set of strings over a alphabet Σ
Example if Σ = { a } following languages can be derived
• Language L1= {a, aaa, aaaaa, aaaaaaa,.......}
• Language L2= { ε, aa, aaaa, aaaaaa,.......}
• Language L3= {a, aaaaa, aaaaaaaaa,.......}
2 a) Obtain an ϵ- NFA which accepts strings consisting of zero or more a’s followed by zero or 5
more b’s followed by zero or more c’s. Marks
Q = {Q0,Q1,Q2}
Σ = {a,b}
Start state – Q0
F : Final state – Q2
δ is subset of 2Q.
Transition Table
δ a b c ɛ
→ Q0 {Q0,Q1} -- -- Q1
Q1 -- {Q1,Q2} -- Q2
* Q2 -- -- Q2 --
Transition Diagram
2b) Define Deterministic Finite Automata. Explain the two preferred notations for
describing the Transition Function with an example.
6
Marks
A DFA is a five-tuple: M = (Q, Σ, δ, q0, F)
Q A finite set of states
Σ A finite input alphabet
q0 The initial/starting state, q0 is in Q
F A set of final/accepting states, which is a subset of Q
δ A transition function, which is a total function from Q x Σ to Q
Preferred notations for describing the Transition Function are as below
(State) Transition diagram :
A state transition diagram or simply a transition diagram is a directed graph which can be
constructed as follows:
1. For each state in Q there is a node.
2. There is a directed edge from node q to node p labeled a iff . (If there
are several input symbols that cause a transition, the edge is labeled by the list of these
symbols.)
3. There is an arrow with no source into the start state.
4. Accepting states are indicated by double circle.
Transition table :
It is a tabular representation of the transition function that takes two arguments (a state and a
symbol) and returns a value (the “next state”).
• Rows correspond to states,
• Columns correspond to input symbols,
• Entries correspond to next states
• The start state is marked with an arrow
• The accept states are marked with a star (*).
Example : DFA to accept strings of a’s and b’s having at least one a
Transition diagram Transition table
δ a b
→ Q0 Q1 Q0
* Q1 Q1 Q1
9
Marks
2c) Obtain a DFA for the following NFA using lazy evaluation method.
δ 0 1
→ Q0 {Q0,Q1} Q1
Q1 {Q2} {Q2}
* Q2 ɸ {Q2}
Procedure of conversion
Start state of DFA : [Q0]
State [Q0]
δn(Q0,0) = [Q0,Q1]
δn(Q0,1) = [Q1]
State [Q1]
δn(Q1,0) = [Q2]
δn(Q1,1) = [Q2]
State [Q2]
δn(Q2,0) = ɸ
δn(Q2,1) = [Q2]
State [Q0,Q1]
δ([Q0,Q1],0) = δn(Q0,0) U δn(Q1,0)
= {Q0,Q1} U {Q2}
= [Q0,Q1,Q2]
δ([Q0,Q1],1) = δn(Q0,1) U δn(Q1,1)
= Q1 U {Q2}
= [Q1 Q2]
State [Q0,Q1,Q2]
δ([Q0,Q1,Q2],0) = δn(Q0,0) U δn(Q1,0) U δn(Q2,0)
= {Q0 Q1} U {Q2} U ɸ
= [Q0 Q1 Q2]
δ([Q0 Q1 Q2],1) = δn(Q0,1) U δn(Q1,1) U δn(Q2,1)
= {Q1} U {Q2} U {Q2}
= [Q1 Q2]
State [Q1,Q2]:
δ([Q1,Q2],0) = δn(Q1,0) U δn(Q2,0)
= {Q0,Q1} U ɸ
= [Q0 Q1]
δ([Q1,Q2],1) = δn(Q1,1) U δn(Q2,1)
= Q2 U {Q2}
= [Q2]
Final states of DFA are [Q2],[Q1 Q2], [Q0 Q1 Q2]
Transition Table of DFA
δ 0 1
→ [Q0] [Q0 Q1] [Q1]
[Q1] [Q2] [Q2]
* [Q2] ɸ [Q2]
[Q0 Q1] [Q0 Q1 [Q1
Q2] Q2]
* [Q0 Q1 [Q0 Q1 [Q1
Q2] Q2] Q2]
* [Q1 Q2] [Q0 Q1] [Q2]
Transition Diagram of DFA
3a) List applications of RE. What are the notations used in UNIX Operation system? List few
Regular expressions with its UNIX notations
Obtain an ∈-NFA for the Regular Expression (a+b)* bb (a+b)*
3b)
(a+b)
(a+b)*
(a+b)*bb
(a+b)*bb(a+b)*
Find the minimized DFA of the following
3c)
Define Pumping Lemma. Prove that below language is not a regular Language. L ={ ai bj | i
>j}
Theorem (Pumping Lemma): Let L be a regular language. Then there exists a constant n such
that for every string w in L such that |w|>=n, w can be split into three strings, w=xyz, such that:
4a) 1. |y| > 0
2. |xy| ≤ n
3. For all k ≥ 0, the string xykz is also in L.
Proof:
Step 1
Let L be regular.
Consider a word w in L.
Step 2
Let w = an+1bn, such that |w|=2n+1. Since 2n+1 > n and L is regular it must satisfy PL.
w can be split into
w : ana(i) bn ∈ L
Step 3
Let i=0
w : an-1a0 bn ∈ L
an-1 bn ∉ L
This Contradicts our assumption that L is regular
Hence the given language is not regular
Develop Regular expressions for the following Languages on Ʃ = { a, b}
i) Accept strings of a’s and b’s whose fifth symbol from the right end is a.
ii) Accept strings of a’s and b’s containing not more than 3 a’s
i) (a+b)* a (a+b) (a+b) (a+b) (a+b)
ii)
4b) b* (a+ ε) b* (a+ ε) b* (a+ ε) b*
Find Regular language accepted by the following FA by eliminating states
4c) Solution
Step 1
Eliminate q2
Q2 is trap state, there is no path from q2 to q1
Resulting Transition Diagram
Regular Expression
0* + 0*11*
or
0* + 0*1+
5a)
What is ambiguous grammar? Explain the Techniques for reducing ambiguity in the
grammar with suitable examples.
Ambiguous Grammar
Let G = (V T P S) be a CFG. The grammar G is ambiguous iff there exists at least 1 string w for
which 2 or more leftmost or rightmost derivations and different parse trees exists.
The following grammar is Ambiguous Grammar
E→E+E
E→E–E
E→E*E
E→E/E
E → id | (E)
The sentence id +id *id can be obtained from left most derivation in two ways as shown below.
E → E+E E → E*E
→ id+E → E+E*E
→ id+E*E → id+E*E
→ id+ id *E → id+id*E
→ id+ id *id → id+ id *id
Elimination of ambiguity using precedence and associativity rule
Arrange the operators in ascending order of along with associativity
Operators Associativity Non Terminal used
+,- LEFT E
*,/ LEFT T
^ RIGHT P
Step 2 : the basic unit of expression is id and parenthesis. Write corresponding production as
F -> id | (E)
Step 3 : the next highest priority is ^ and is right associative. So write P production as
P -> F ^ P | F
Step 4 : the next highest priority operators are * and / and are left associative. So write T production
as
T -> T* P | T/P | P
Step 5 : + and – are next priority operators and left associative so write E production as E -> E +
T|E–T|T
Step 6 : the final unambiguous grammar
E -> E + T | E – T | T
T -> T* P | T/P | P
P -> F ^ P | F
F -> id | (E)
5b)
Show that the following grammar is ambiguous by taking the string aab.
S → aS | aSbS | ϵ
LMD 1
S → aS
→ aaSbS ; S → aSbS
→ aa ϵ b ϵ ;S → ɛ
→ aab
LMD 2
S → aSbS
S → aaSbS ; S → aS
→ aa ϵ b ϵ ;S → ɛ
→ aab
Since there are two leftmost derivations the
grammar is ambiguous
5c) Design the Context Free Grammar for the following Languages.
i) To accept the set of all strings with no more than three a’s when Ʃ = {a, b}.
ii) To accept the set of strings with any number of a’s and b’s with at least one a.
i) S → B | BaB | BaBaB | BaBaBaB
B → bB | b
G = { {S,B},{a,b}, P, S }
ii) S → aA | a
A → aA | bA | ɛ
