Examples of DFA
This lecture discusses more than 30 examples of DFA. But you make sure that you have already covered the topic of DFA. There are six different categories are selected for examples of DFA, which are listed below
- Accept Only given Input
- Start and Ends with
- Contains string
- Specific Length
- Divisibility
- Even and odd string
Let’s explain all of these DFA examples in sequence in TOC.
Example 1:
Design a DFA over ∑ = {0, 1} that accepts the only input a string “10”.
Solution:
In the above example, the language contains only one string given below
L= {10}
DFA that accepts the only input a string “10” is given below
Example:2
Construct a DFA with ∑ = {a, b} that accepts the only input “aaab”.
Solution:
The given question provides the following language
L= {aaab}
The following diagram represents the DFA accepter for L= {aaab}.
Example:3
Construct DFA, which accept all the string over alphabets ∑ {0,1} that start with “0”.
Solution:
The given question provides the following language
L = {0, 01, 00, 010, 011, 000, 001,…, }
Let’s draw the DFA, which accepts all the strings starting with “0”.
Example:4
Construct DFA, which accept all the string over alphabets ∑ {0,1} that start with “01”.
Solution:
The given question provides the following language
L = {01, 010, 011, 0100, 0101, 0110, 0111}
Let’s draw the DFA which accepts all the strings of the above language
Example:5
Construct DFA, which accepts all the strings over alphabets ∑ {0,1} that ends with “0”.
Solution:
The given example provides the following language
L = {0, 10, 00, 000, 010, 100, 110, …, }
Let’s draw the DFA, which accepts all the strings that end with “0”.
Example:6
Construct DFA, which accept all the string over alphabets ∑ {0,1} that end with “10”.
Solution:
The given question provides the following language
L = {10, 010, 110, 0010, 0110, 1010, 1110,…., }
DFA, which accepts all the strings that end with “10” is given under
Example:7
Construct a DFA with sigma ∑ = {0, 1}, accepts those string which starts with one and ends with 0.
Solution:
The given question provides the following language
L= {10, 1100,1010, 1110, 100010, 1000101110,…, }
The following diagram represents the DFA accepter for the above language.
Note: The above automata machine does not accept those strings that start and end with the same input as “10001”.
Example:8
Construct DFA, which accepts all the strings over ∑ {0,1} where each contains “0”.
Solution:
The given question provides the following language
L= {0, 01, 10, 00,001,101,000, …., }
Let’s draw the DFA, which accepts all the strings containing “0”.
Example:9
Construct DFA, which accept all the string over alphabets ∑ {0,1} where each string contains “00”.
Solution:
The given question provides the following language
L= { 00, 000, 100, 001, 1100, 0011, 0010, 1001,……, }
Let’s draw the DFA which accepts all the strings of the above language
Example:10
Construct a DFA with sigma ∑ = {0, 1}, accepts all strings that contain three consecutive 0’s.
Solution:
The given question provides the following language
L= {000, 1000,0001, 111000, 10001, …, }
DFA, which accepts all the strings that contain three consecutive 0’s, is given under
Example:11
Construct DFA, which accept all the string over alphabets ∑ {0,1} where each string contains “101” as a substring.
Solution:
The given question provides the following language
L= {101, 0101, 1101, 1010, 1010, 01010, 01011,……, }
Let’s draw the DFA which accepts all the strings of the above language
Example:12
Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is exactly 2.
Solution:
The given question provides the following language
L= {00, 01, 10, 11}
The following diagram represents the DFA accepter for the language language where the length of each string is exactly two.
Example:13
Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is ≥ 2.
Solution:
The given question provides the following language
L = {00, 01, 10, 11, 000, 011, 010, 100, 101, 111, 0000, ……, }
The following diagram represents the DFA accepter for the language language where the length of each string is ≥ 2.
Example:14
Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is ≤ 2
Solution:
The given question provides the following language
L = {0, 1, 00, 01, 10, 11}
The following diagram represents the DFA accepter for the language where the length of each string is ≤ 2
Example:15
Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is EVEN.
Solution:
The given question provides the following language
L = {00, 01, 10, 11, 0000, 1111, 0011, ……, }
The following diagram represents the DFA accepter for the language where the length of each string is even.
Example:16
Construct DFA, which accept all the string over alphabets ∑ {0,1} where the length of each string is ODD.
Solution:
The given question provides the following language
L = {0, 1, 000, 111, 011, 100, ……, }
The following diagram represents the DFA accepter for the language where the length of each string is odd.
Example:17
Construct DFA, which accepts all the string over alphabets ∑ {0,1} where binary integers divisible by 3
Solution:
The given question provides the following language
L = {0, 11, 110, 1001, 1100, 1111, ……, }
The explanation for string 1001 is given below.
1001= 9, 9/3 = 3; hence, 1001 is divisible by 3.
The following diagram represents the DFA accepter for the language where binary integers are divisible by three.
Example:18
Construct DFA, which accepts all the string over alphabets ∑ {0,1} where binary integers divisible by 4
Solution:
The given question provides the following language
L = {0, 100, 1000, 1100, 10000,……, }
The explanation for string 10000 is given below.
10000= 16, 16/4 = 4, hence 10000 is divisible by 4.
The following diagram represents the DFA accepter for the language where binary integers are divisible by four.
DFA Example 19:
Draw a DFA for the language that accepts strings containing neither ’00’ nor ’11’ as a substring over the input alphabet ∑ = {0, 1}.
Solution:
The given question provides the following language (L) and DFA diagram
L={0,1,10,010,1010,01010,101010,0101010,10101010,010101010,…..}
DFA Example 20:
Design a DFA that accepts strings with ’01’ or ’10’ as a substring over input alphabets ∑ = {0, 1}.
Solution:
The given question provides the following language (L) and DFA diagram
L={001,110,1110,0010,0001,1101,…..}
DFA Example 21
Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings ending in either ’01’ or ’10’.
Solution:
The given question provides the following language (L) and DFA diagram
L={01,10, 010, 101, 001, 110…..}
DFA Example 22
Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings containing exactly two ‘0’.
Solution:
The given question provides the following language (L) and DFA diagram
L={00, 100, 001, 1010, 0101, 11100,…….}
DFA Example 23
Design a DFA with sigma ∑ = {0, 1} for the language accepting strings containing at least two ‘0’.
Solution:
The given question provides the following language (L) and DFA diagram
L={00,001,000,0011,0010,0001,0000,1100, 1001…..}
DFA Example 24
Draw a DFA with sigma ∑ = {0, 1} for the language accepting strings containing at most two ‘0’.
Solution:
The given question provides the following language (L) and DFA diagram
L={0,1,10,01,001,1001,1011,1101, …..}
DFA Example 25
Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings starting and ending with ‘0’ always.
Solution:
The given question provides the following language (L) and DFA diagram
L={0,00,010,000, 0110, 0100…..}
DFA Example 26
Design a DFA with sigma ∑ = {0, 1} for the language accepting strings starting and ending with different characters.
Solution:
The given question provides the following language (L) and DFA diagram
L={01,10,011,100,…..}
DFA Example 27
Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings starting and ending with the same characters.
Solution:
The given question provides the following language (L) and DFA diagram
L={00,11,101,010,…..}
DFA Example 28
Design a DFA with sigma ∑ = {0, 1} for the language accepting strings containing an odd number of total zeros (or odd binary numbers strings).
Solution:
The given question provides the following language (L) and DFA diagram
L={0,01,10, 101, 010, 1011, 1110,…..}
DFA Example 29
Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings starting with ‘00’ or ’11’
Solution:
The given question provides the following language (L) and DFA diagram
L={00,11,000,111, 110,0001,0010, …..}
DFA Example 30
Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings ending with ‘0011’.
Solution:
The given question provides the following language (L) and DFA diagram
L={0011,00011,10011,110011,000011,…..}
DFA Example 31
Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings ending with ‘0110’ .
Solution:
The given question provides the following language (L) and DFA diagram
L={0110,10110,00110,110110,000110,…..}
DFA Example 32
Construct a DFA with sigma ∑ = {0, 1} for the language accepting strings ending with ‘00’.
Solution:
The given question provides the following language (L) and DFA diagram
L={00,000,0100,01100,01000…..}
Example:33
Design a DFA with sigma ∑ = {a, b}, accepts those strings that have an even number of “0’s” and an even number of “1’s”.
Solution:
The given question provides the following language
L= { ε, 00, 11, 0101, 1001, 0011, 00001111, 11110000,…., }
Note: Epsilon (ε) represents zero, which is even.
Let’s draw the DFA which accepts all the strings of the above language
In Above DFA,
- If state q1 becomes final instead of q0, DFA will accept all those strings with Odd “0” and even “1”.
- And if state q2 becomes final instead of q0, then DFA will accept all those strings with even “0” and odd “1”.
- And If state q3 becomes final instead of q0, then DFA will accept all those strings with odd “0” and odd “1”.
