Regular Expression to DFA
Converting a Regular Expression (RE) to a Deterministic Finite Automaton (DFA) is a very important concept in the Theory of Computation. Let’s see more than 40 examples of Regular Expression to DFA conversion.
Regular Expression to DFA Example: 01
Convert the Regular Express RE = a to DFA
Solution
- RE = a
- Strings = {a}
- L = String “a” is accepted only
Regular Express RE = a to DFA is given below
Regular Expression to DFA Example: 02
Convert the Regular Express RE =a* to DFA
Solution
- RE = a*
- Strings = {ε, a, aa, aaa, aaaa, ……}
- L = zero or more occurrences of ‘a’
Regular Express RE =a* to DFA is given below
Regular Expression to DFA Example: 03
Convert the Regular Express RE =a+ to DFA
Solution
- RE = a+
- Strings = {a, aa, aaa, aaaa, ……}
- L = One or more occurrences of ‘a’
Regular Express RE =a+ to DFA is given below
Regular Expression to DFA Example: 04
Convert the Regular Express RE = a+b to DFA
Solution
- RE = (a+b)
- Strings = {a,b}
- L = String “a” or “b” is accepted only
Regular Express RE = a+b to DFA is given below
Regular Expression to DFA Example: 05
Convert the Regular Express RE = (a+b)* to DFA
Solution
- RE = (a+b)*
- Strings = {ε, a, b, aa, ab, ba, bb, aaa, abb, …}
- L = zero or more occurrences of ‘a’ or ‘b’
Regular Express RE = (a+b)* to DFA is given below
Regular Expression to DFA Example: 06
Convert the Regular Express RE = (a+b)+ to DFA
Solution
- RE = (a+b)+
- Strings = {a, b, aa, ab, ba, bb, aaa, abb, …}
- L = One or more occurrences of ‘a’ or ‘b’
Regular Express RE = (a+b)+ to DFA is given below
Regular Expression to DFA Example: 07
Convert the Regular Express RE = (10+1)* to DFA
Solution
- RE = (10+1)*
- Strings = {ε, 10, 1, 10101, 111101, 100110101111 ,…}
- L = Combination of ‘10’, and ‘1’, including the empty string
Regular Express RE = to DFA is given below
Regular Expression to DFA Example: 08
Convert the Regular Express RE = (01+10+1)* to DFA
Solution
- RE = (01+10+1)*
- Strings = {ε, 01, 10, 1, 01101, 111101, 100110101111 ,…}
- L = Combination of ‘01’, ‘10’, and ‘1’, including the empty string
Regular Express RE = (01+10+1)* to DFA is given below
Regular Expression to DFA Example: 09
Convert the Regular Express RE = (a+b+c+d)* to DFA
Solution
- RE = (a+b+c+d)*
- Strings = {ε, a, b, c, d, ab, ac, ad, ba, bb, …, abcd, dbca, …}
- L = Any combination of ‘a’, ‘b’, ‘c’, and ‘d’, including the empty string
Regular Express RE = (a+b+c+d)* to DFA is given below
Regular Expression to DFA Example: 10
Convert the Regular Express RE = (a+b+c+d)+ to DFA
Solution
- RE = (a+b+c+d)+
- Strings = {a, b, c, d, ab, ac, ad, ba, bb, …, abcd, dbca, …}
- L = Any combination of ‘a’, ‘b’, ‘c’, and ‘d’, empty string not allowed
Regular Express RE = (a+b+c+d)+ to DFA is given below
Regular Expression to DFA Example: 11
Convert the Regular Express RE =(ab+bb+cc+dd)* to DFA
Solution
- RE = (ab+bb+cc+dd)*
- Strings = {ε, ab, bb, cc, dd, abbb, abcc, ccdd, ddbbccab,…}
- L = Combination of ‘ab’, ‘bb’, ‘cc’, and ‘dd’, including the empty string
Regular Express RE = (ab+bb+cc+dd)* to DFA is given below
Regular Expression to DFA Example: 12
Convert the Regular Express RE =101 + (0+1)*1 to DFA
Solution
- RE = 101 + (0+1)*1
- Strings = {101, 1, 01, 001, 101, 0001, 1111, …}
- L = strings that are either exactly ‘101’ or end with ‘1’ over {0,1}
Regular Express RE = 101 + (0+1)*1 to DFA is given below
Regular Expression to DFA Example: 13
Convert the Regular Express RE =11 + 00 + 0 + 10* to DFA
Solution
- RE = 11 + 00 + 0 + 10*
- Strings = {11, 00, 0, 10, 100, 1000, 10000, …}
- L = Strings that are either:
- Exactly “11”,
- Exactly “00”,
- Exactly “0”,
- Or “1” followed by zero or more “0”s
Regular Express RE = 11 + 00 + 0 + 10* to DFA is given below
Regular Expression to DFA Example: 14
Convert the Regular Express RE =1(0 + 11) + 0(00 + 1) to DFA
Solution
- RE = 1(0 + 11) + 0(00 + 1)
- Strings = {10, 111, 000, 01}
- L = strings that are either
- ‘1’ followed by ‘0’ or ’11’, OR ‘
- 0’ followed by ’00’ or ‘1’
Regular Express RE = 1(0 + 11) + 0(00 + 1) to DFA is given below
Regular Expression to DFA Example: 15
Convert the Regular Express RE =ba + (aa + b)* to DFA
Solution
- RE = ba + (aa + b)*
- Strings = {ε, ba, b, aa, aaaabb, aab, bbaa, bbaab, …}
- L = strings that are either ‘ba’, or any number of repetitions of ‘aa’ and ‘b’
Regular Express RE = ba + (aa + b)* to DFA is given below
Regular Expression to DFA Example: 16
Convert the Regular Express RE =aa + ba + (aa + b)* to DFA
Solution
- RE = aa + ba + (aa + b)*
- Strings = {ε, aa, ba, b, bb, aaaabb, aab, bbaa, bbaab, …}
- L = strings that are either ‘aa’, ‘ba’, or any number of repetitions of ‘aa’ and ‘b’
Regular Express RE = aa + ba + (aa + b)* to DFA is given below
Regular Expression to DFA Example: 17
Convert the Regular Express RE = (00)*(0 + 1) + (1)* to DFA
Solution
- RE = (00)*(0 + 1) + (1)*
- Strings = {ε, 0, 1, 11, 111, 001, 0001, 0000, 000001, …}
- L = strings that are either:
- Zero or more repetitions of “00” followed by ‘0’ or ‘1’, or
- Zero or more repetitions of ‘1’ alone
Regular Express RE = (00)*(0 + 1) + (1)* to DFA is given below
Regular Expression to DFA Example: 18
Convert the Regular Express RE = (001)* + (00) to DFA
Solution
- RE = (001)* + (00)
- Strings = {ε, 001, 001001, 001001001,…………, 00}
- L = Language contains either: the exact string “00”, or any number (including zero) of the substring “001” repeated.
Regular Express RE = (001)* + (00) to DFA is given below
Regular Expression to DFA Example: 19
Convert the Regular Express RE = a(a+b)* to DFA
Solution
- RE = a(a+b)*
- Strings = {a, ab, ab, aaa, abb, aba, abb, aaab, …}
- L = start with ‘a’ followed by any combination of ‘a’ or ‘b’
Regular Express RE = a(a+b)* to DFA is given below
Regular Expression to DFA Example: 20
Convert the Regular Express RE =101*(0+1)* to DFA
Solution
- RE = 101*(0+1)*
- Strings = {10, 10101, 1010, 10101, 10100, 101000, …}
- L = start with ’10’, followed by zero or more ‘1’s, and then any combination of ‘0’ or ‘1’
Regular Express RE = 101*(0+1)* to DFA is given below
Regular Expression to DFA Example: 21
Convert the Regular Express RE =bab(a+b)* to DFA
Solution
- RE = bab(a+b)*
- Strings = {bab, baba, babb, babaa, babab, babba, babbb, babaaa, abb, …}
- L = start with ‘bab’ followed by any combination of ‘a’ or ‘b’
Regular Express RE = bab(a+b)* to DFA is given below
Regular Expression to DFA Example: 22
Convert the Regular Express RE = aa(aba + bab)* to DFA
Solution
- RE = aa(aba + bab)*
- Strings = {aa, aaaba, aaababab, aababababab, …}
- L = start with ‘aa’, followed by zero or more repetitions of ‘aba’ or ‘bab’
Regular Express RE = aa(aba + bab)* to DFA is given below
Regular Expression to DFA Example: 23
Convert the Regular Express RE =(a(bb)*)(a+b)* to DFA
Solution
- RE = (a(bb)*)(a+b)*
- Strings = {a, abb, abba, abba, abbb, aa, ab, aba, abbbaaab,….}
- L = start with ‘a’ followed by zero or more ‘bb’ pairs, then any combination of ‘a’ or ‘b’
Regular Express RE = (a(bb)*)(a+b)* to DFA is given below
Regular Expression to DFA Example: 24
Convert the Regular Express RE =1(0+1)(00+11)* to DFA
Solution
- RE = 1(0+1)(00+11)*
- Strings = {10, 11, 1000, 1011, 1111, 1011000011,…..}
- L = start with ‘1’, followed by either ‘0’ or ‘1’, and then zero or more repetitions of ’00’ or ’11’
Regular Express RE = 1(0+1)(00+11)* to DFA is given below
Regular Expression to DFA Example: 25
Convert the Regular Express RE = a+b+c+(ab+bb+cc)* to DFA
Solution
- RE = a+b+c+(ab+bb+cc)*
- Strings = {a, b, c, cab, cbb, ccc, cabbb, cabab, cbbcc, cabbbccab, …}
- L = Exactly ‘a’, ‘b’, Or ‘c’ followed by zero or more repetitions of “ab”, “bb”, or “cc”
Regular Express RE = a+b+c+(ab+bb+cc)* to DFA is given below
Regular Expression to DFA Example: 26
Convert the Regular Express RE =a+b+c+d(ab+bb+cc+dd)* to DFA
Solution
- RE = a+b+c+d(ab+bb+cc+dd)*
- Strings = { a, b, c, d, dab, dbb, dcc, ddd, , dbbabdd, …}
- L = either exactly ‘a’, ‘b’, or ‘c’, or start with ‘d’ followed by zero or more repetitions of ‘ab’, ‘bb’, ‘cc’, or ‘dd’
Regular Express RE = a+b+c+d(ab+bb+cc+dd)* to DFA is given below
Regular Expression to DFA Example: 27
Convert the Regular Express RE =aba(a + b)* + bab (a + b)* to DFA
Solution
- RE = aba(a + b)* + bab (a + b)*
- Strings = {aba, bab, abab, abaa, ababb, baba, babb, …}
- L = start with ‘aba’ or ‘bab’, followed by any combination of ‘a’ or ‘b’
Regular Express RE = aba(a + b)* + bab (a + b)* to DFA is given below
Regular Expression to DFA Example: 28
Convert the Regular Express RE =(a+b+c+d)*ab to DFA
Solution
- RE = (a+b+c+d)*ab
- Strings = {ab, aab, cab, dab, cdab, ddab, bacdab, …}
- L = Strings that end with ‘ab’ and may have any combination of ‘a’, ‘b’, ‘c’, or ‘d’ before it
Regular Express RE = (a+b+c+d)*ab to DFA is given below
Regular Expression to DFA Example: 29
Convert the Regular Express RE =(aaa+bbb)*ba to DFA
Solution
- RE = (aaa+bbb)*ba
- Strings = {ba, aaabbbba, bbbba, aaaba, aaabbbaaaba, …}
- L = Strings formed by zero or more repetitions of ‘aaa’ or ‘bbb’, followed by ‘ba’
Regular Express RE = (aaa+bbb)*ba to DFA is given below
Regular Expression to DFA Example: 30
Convert the Regular Express RE =(a+b+c)*abc to DFA
Solution
- RE = (a+b+c)*abc
- Strings = {abc, aabc, babc, cabc, ababc, ccbabc, …}
- L = strings that end with ‘abc’ and may have any combination of ‘a’, ‘b’, or ‘c’ before it
Regular Express RE = (a+b+c)*abc to DFA is given below
Regular Expression to DFA Example: 31
Convert the Regular Express RE = (0+1)*101* to DFA
Solution
- RE = (0+1)*101*
- Strings = {10, 101, 1011, 0010, 1101, 00010111, …}
- L = strings that contain ’10’ followed by zero or more ‘1’s, with any combination of ‘0’ or ‘1’ before it
Regular Express RE = (0+1)*101* to DFA is given below
Regular Expression to DFA Example: 32
Convert the Regular Express RE = (a+b)*a(a+b)b to DFA
Solution
- RE = (a+b)*a(a+b)b
- Strings = {aab, ababb, aaab, babaab, …}
- L = Strings that contain any combination of ‘a’ and ‘b’, followed by an ‘a’, then any one symbol from {a, b}, and ending with a ‘b’
Regular Express RE = (a+b)*a(a+b)b to DFA is given below
Regular Expression to DFA Example: 33
Convert the Regular Express RE =(00+11)*1(0+1) to DFA
Solution
- RE = (00+11)*1(0+1)
- Strings = {10, 11, 0010, 0011, 00110010, 001111, …}
- L = Strings that consist of zero or more repetitions of ’00’ or ’11’, followed by a ‘1’, and ending with either ‘0’ or ‘1’
Regular Express RE = (00+11)*1(0+1) to DFA is given below
Regular Expression to DFA Example: 34
Convert the Regular Express RE =1(1 + 0)*1 + 0(1 + 0)*0 to DFA
Solution
- RE = 1(1 + 0)*1 + 0(1 + 0)*0
- Strings = {11, 101, 1001, 1101, 010, 0010, 0000, 0110, …}
- L = Strings that start and end with the same bit (either ‘1’…‘1’ or ‘0’…‘0’), with any combination of ‘0’ or ‘1’ in between
Regular Express RE = 1(1 + 0)*1 + 0(1 + 0)*0 to DFA is given below
Regular Expression to DFA Example: 35
Convert the Regular Express RE =(11)(0 + 1)(00) to DFA
Solution
- RE = (11)(0 + 1)(00)
- Strings = {11000, 11100}
- L = strings that start with ’11’, followed by either ‘0’ or ‘1’, and end with ’00’
Regular Express RE = (11)(0 + 1)(00) to DFA is given below
Regular Expression to DFA Example: 36
Convert the Regular Express RE =00(11)*101 to DFA
Solution
- RE = 00(11)*101
- Strings = {00101, 0011101, 001111101, …}
- L = Strings that start with ’00’, followed by zero or more repetitions of ’11’, and ending with ‘101’
Regular Express RE = 00(11)*101 to DFA is given below
Regular Expression to DFA Example: 37
Convert the Regular Express RE = aba(aa + b)*ba to DFA
Solution
- RE = aba(aa + b)*ba
- Strings = {ababa, ababba, ababba, ababbaaaaba, …}
- L = Start with ‘aba’, followed by any number of repetitions of ‘aa’ or ‘b’, and end with ‘ba’
Regular Express RE = aba(aa + b)*ba to DFA is given below
Regular Expression to DFA Example: 38
Convert the Regular Express RE =b*(aaa + bbb)*ba to DFA
Solution
- RE = b*(aaa + bbb)*ba
- Strings = {ba, bba, bbaaaba, bbba, bbbbbbba, baaabbbba, …}
- L = strings that start with zero or more ‘b’s, followed by zero or more repetitions of ‘aaa’ or ‘bbb’, and end with ‘ba’
Regular Express RE = b*(aaa + bbb)*ba to DFA is given below
Regular Expression to DFA Example: 39
Convert the Regular Express RE = a(a + b)*ba + a to DFA
Solution
- RE = a(a + b)*ba + a
- Strings = {a, aba, abba, aaba, aaabba, abbba, …}
- L = strings that are either a single ‘a’ or start with ‘a’, followed by any combination of ‘a’ or ‘b’, and ending with ‘ba’
Regular Express RE = a(a + b)*ba + a to DFA is given below
Regular Expression to DFA Example: 40
Convert the Regular Express RE = 0 + 1(0 + 1)*10 to DFA
Solution
- RE = 0 + 1(0 + 1)*10
- Strings = {0, 110, 1010, 10010, 1110, 100110, …}
- L = strings that are either exactly ‘0’ or start with ‘1’, followed by any combination of ‘0’ and ‘1’, and end with ’10’
Regular Express RE = 0 + 1(0 + 1)*10 to DFA is given below
