Scribd
Upload
100 views16 pages

DFA Design Examples

This document provides solutions to example problems of designing deterministic finite automata (DFAs) that accept various languages over different alphabets. The examples include DFAs that accept languages of strings with a certain number or pattern of symbols like strings divisible by 3, strings with an odd number of b's, strings of length 2 or at least length 2, strings of the form anbm, and strings containing or avoiding certain subsequences.

Uploaded by

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

DFA Design Examples

This document provides solutions to example problems of designing deterministic finite automata (DFAs) that accept various languages over different alphabets. The examples include DFAs that accept languages of strings with a certain number or pattern of symbols like strings divisible by 3, strings with an odd number of b's, strings of length 2 or at least length 2, strings of the form anbm, and strings containing or avoiding certain subsequences.

Uploaded by

Abhishek Rai
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

Some solved examples of

Design of a DFA
Construct a DFA that accepts all strings from the language

L = { ^ , a, aa, aaa, aaaa, . . .}


Construct a DFA that accepts all strings from the language

L = {a, aa, aaa, aaaa, . . .}

Solution:
Construct a DFA that accepts all strings from the language

L = {strings of size divisible by 3} over Σ= {a}

Solution:

L: {^, aaa, aaaaaa, aaaaaaaaa, . . .}


Construct a DFA that accepts all strings from the language

L = {strings with odd number of b’s} over Σ= {a,b}

Solution:
Construct a DFA which accepts set of all strings over Σ={a,b} of length 2

Solution:
L = {aa, ab, ba, bb}
Design a DFA that accepts the unary number divisible by 3
Construct a DFA which accepts set of all strings over Σ={a,b} of length ≥2

Solution:
Design a DFA such that:

L = {anbm | n,m ≥ 1} over Σ={a, b}

Solution:

Language L = {ab, aab, aaab, abbb, aabb, aaaabbbb, ...}


Design a DFA that
accepts all strings of 0’s and 1’s that contain substring 01
Design a DFA that
accepts all strings of a’s and b’s with
even number of a’s and even number of b’s
(Hint: Strings may contain only even number of a’s <or> only even number of b’s <or> both even number of a’s and even number of b’s)
Design a DFA that
accepts all strings over {0,1} that does not contain three consecutive 1’s
Design a DFA that
accepts all strings of 0’s and 1’s that ends with 01
Design a DFA that
accepts set of strings in which number of a’s are divisible by 3 over {a, b}
Design a DFA that
accepts set of strings which starts with 01
Design a DFA that
accepts the strings containing exactly four 1’s over {0, 1}

You might also like