Scribd
Upload
31 views12 pages

DFA Construction Techniques Explained

The document discusses drawing deterministic finite automata (DFAs) with certain properties: 1) It provides a 4-step process for drawing DFAs: (1) accept strings, (2) transition diagram, (3) transition table, (4) definitions. 2) It gives an example of a DFA over the alphabet {a,b} that starts with 'a' as an illustration. 3) It provides some hints for drawing DFAs, such as the number of states equals the number of input symbols plus one, and each input symbol transitions from each state exactly once.

Uploaded by

Harshit Singh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
31 views12 pages

DFA Construction Techniques Explained

The document discusses drawing deterministic finite automata (DFAs) with certain properties: 1) It provides a 4-step process for drawing DFAs: (1) accept strings, (2) transition diagram, (3) transition table, (4) definitions. 2) It gives an example of a DFA over the alphabet {a,b} that starts with 'a' as an illustration. 3) It provides some hints for drawing DFAs, such as the number of states equals the number of input symbols plus one, and each input symbol transitions from each state exactly once.

Uploaded by

Harshit Singh
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Theoretical Computer Science

Lecture - 2
3 July 2020
Asst. Professor Nilima Shingate
DFA

1) Draw DFA ,Start with


2) Draw DFA , End with
3) Draw DFA , Start with and End with
4) Draw DFA having substring
5) Draw DFA not having substring
6) Draw DFA with all possibilities
(Combination of All)
7) Having common substring *
To Draw DFA 4 Steps to follow :

 Step I) Accepted Strings

 Step 2) Transition Diagram

 Step 3) Transition Table

 Step 4) Definition of DFA


1. Draw DFA , Start With Sum

 Draw DFA over a language { a, b} which st.


with ‘a’.

Step I) Accepted Strings


a, aa, ab , aabbbbb, aaaaaa, a……

Anything
a will do
 CL UE / HINT :

1) Total No. of States = total no. of input


Symbol + 1

In above Example

2 = 1 + 1

Note : Error State will not get counted.


 CL UE / HINT :

2 ) All input symbol from each state should


go out once. i.e. Out degree of each
input symbol should be One.

if input symbols are {a , b, c } in the sum


then
a
b
q0
c
 CL UE / HINT :

3 ) In degree can be anything i.e. more


than One.

if input symbols are {a , b, c } in the sum


then
a
a
b b
q0
c
b
 Step 2 ) Transition Diagram

a,b
a
q0 q1
q1

b
a,
b
qE
 Step 3) Transition Table :

∂ a b

q0 q1 qE

q1 q1 q1

qE qE qE
 Step 4) Definition :
M = {Q, ∑, ∂, q0 , F} Five Tuples
Q = {q0,q1,qE}
∑ = {a,b}
∂ = Transition mapping Function
Q→Q X∑
q0 = {q0}
F = {q1}

Final state shows with double circle.


Solve :

 Draw DFA over a language { 0 , 1 } which st.


with ‘1’.

 Draw DFA over a language { p,q,r} which st.


with ‘q’.

 Draw DFA over a language { x,y,z} which st.


with ‘z’.
THANK YOU !!!

You might also like