Applications of DFA
Pattern Matching : Find the number of occurrences of pattern P
= abab in text T = aababababba.
Given a text T and pattern P, the problem is to find if P appears in T. And, if it appears, how
many times it appears? A DFA can be constructed over the pattern and the text T can be run
over the DFA. Whenever final state is reached, the repeat count is incremented.
We can design a DFA for the pattern "abab" in the same manner we discussed. The DFA is
given below.
Each state is named by part of the pattern that has been observed so far. We initialize a
variable count to 0. The count will be incremented whenever the final state abab is reached.
δ(ε, aababababba) = δ(a, ababababba) [count = 0]
= δ(a, babababba) [count = 0]
= δ(ab, abababba)
= δ(aba, bababba)
= δ(abab, ababba) [count = 1]
= δ(aba, babba)
= δ(abab, abba) [count = 2]
= δ(aba, bba)
= δ(abab, ba) [count = 3]
= δ(ε, a)
= δ(a, ε)
=a
Thus the number of occurrences can be computed as 3. With additional logic over the DFA,
the start positions of the pattern can be computed too. The famous Knuth-Morris-Pratt (KMP)
algorithm provides a way to compute the DFA for the pattern in time linear to its length.
Vending Machine : DFA can be used to model real-life scenarios. Here, we see how a
vending machine is modelled using DFA. A vending machine accepts inputs in the form of
coins or denominations and dispenses items based on the total amount collected and the
selection made by the customer. The DFA below is an example of a vending machine that
accepts coins of two denominations 5 and 10 and selection of three items Tea, Cookie and
Coke that costs Rs. 15, Rs. 20 and Rs. 25 respectively.
Although, the state machine could be designed in an elaborate manner, this one gives a fair
idea how it can be used to design a real-life scenario.
1. NFA that accepts strings that end with abb. Σ = {a, b}
Read any number of a's and b's and remain in q0 until you "abb" at the end.
L = { abb, aabb, babb, aaabb, ababb, baabb, bbabb, ……}
As an example, consider the string: aaaaabb. i.e. Five a's followed by two b's. The NFA remains in
q0 while reading the first four a's. When it reads the fifth a, it jumps to q1.
δ(q0,aaaaabb) → δ({q0,q1},aaaabb) → δ({q0,q1},aaabb) → δ({q0,q1},aabb) → δ({q0,q1},abb) →
δ({q0,q1},bb) → δ({q0,q2},b) →{q0,q3}
Note that there are two transitions possible from q0 for the input symbol 'a' in the above example.
i.e. δ(q0,a) = {q0, q1}. In other words, a transition in an NFA is a movement from one state to a set of
states.
Contrast this with the DFA directly constructed (shown below for convenience)
You can observe that the NFA is far simpler to construct than the original DFA. It doesn't however
imply, NFA is more powerful compared to DFA. i.e., if a NFA can be designed for a problem, it can
easily be converted to an equivalent DFA.
2. NFA that accepts strings that contains abb. Σ = {a, b}
3. NFA that accepts strings that does not contain abb. Σ = {a, b}
4. NFA that accepts strings that starts with two a's and ends with two a's. Σ = {a, b}
5. NFA that accepts strings that end with "ab" or "ba". Σ = {a, b}
6. NFA that accepts strings that starts and ends with different symbols Σ = {a, b}