Scribd
Upload
123 views1 page

DFA Construction Tutorial and Examples

The document outlines a tutorial for constructing Deterministic Finite Automata (DFA) for various string conditions over the alphabet ∑={a,b} and ∑={0,1}. It includes tasks such as accepting strings with specific counts of 'a's and 'b's, strings with certain starting and ending symbols, and strings ending with particular sequences. Each task provides a distinct requirement for the DFA to fulfill.

Uploaded by

Akshat Gupta
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
123 views1 page

DFA Construction Tutorial and Examples

The document outlines a tutorial for constructing Deterministic Finite Automata (DFA) for various string conditions over the alphabet ∑={a,b} and ∑={0,1}. It includes tasks such as accepting strings with specific counts of 'a's and 'b's, strings with certain starting and ending symbols, and strings ending with particular sequences. Each task provides a distinct requirement for the DFA to fulfill.

Uploaded by

Akshat Gupta
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

Tutorial 1 (DFA)

1. Construct a DFA that accepts any string over ∑={a,b} that contains at least two a’s.
2. Construct a DFA that accepts any string over ∑={a,b} that contains exactly two a’s.
3. Construct a DFA that accepts any string over ∑={a,b} that contains at most two a’s.
4. Construct a DFA that accepts any string over ∑={a,b} that contains at least two a’s and exactly one b.
5. Construct a DFA that accepts any string over ∑={a,b} that contains at least two a’s and at most 2 b’s.
6. Construct a DFA that accepts any string over ∑={a,b} that contains even number of a’s.
7. Construct a DFA that accepts any string over ∑={a,b} in which starting and last symbol should be
similar.
8. Construct a DFA that accepts any string over ∑={a,b} in which starting and last symbol should be
different.
9. Construct a DFA that accepts any string over ∑={a,b} in which second last symbol should be a, and
string W>=2.
10. Construct a DFA for the language accepting strings ending with ‘abb’ over input alphabets ∑ = {a, b}
11. Construct a DFA for the language accepting strings ending with ’01’ over input alphabets ∑ = {0, 1}
12. Construct a DFA for the language accepting strings ending with ‘abba’ over input alphabets ∑ = {a, b}
13. Construct a DFA for the language accepting strings ending with ‘0011’ over input alphabets ∑ = {0, 1}
14. Construct a DFA with ∑ = {0, 1} accepts those string which starts with 1 and ends with 0.
15. Construct a DFA with ∑ = {0, 1} accepts the set of all strings with three consecutive 0's.

You might also like