Regular Languages
Contents
Regular Languages¶
The set of inputs a DFA accepts is a language. More specifically, the set of inputs accepted by a DFA is called a regular language. Not all languages can be accept by DFA. Regular Languages are the subset of all languages that DFAs can work with.
The toll booth gate is a regular language. The following strings are all accepted by the DFA. A string is just a set of symbols in order. This is a little more abstract than our previous definition of string. The two map easily. An assembly string is just a set of symbols that can be represented as characters in the programming languages.
All the following strings are accepted by the toll booth gate. They all cause the gate to raise.
NNNNNN
NNNND, NNNDN, NNDNN, NDNNN, DNNNN
NNDD, NDND, DNDN, DDNN, DNND, NDDN
DDD
QN, NQ
This language is an infinite language. We can in theory put millions of dollars in. Our DFA would be fine with this. Hopefully, the real world would stop this from happening. As far as the toll booth language is concerned, it would also accept NQNNNDDDNNNNDNDN.
DFA Computational Features¶
A DFA only needs a fixed amount of memory. It needs to know three things.
A string with the input
A counter to track the current position in the string
A counter to track the current state
The number of states the machine can be in is finite. We know ahead of time how many bits we need to track the state. We just look at the table and change the state for each character.
A DFA looks at each character in the string in order. It transitions based on the transition table. Once it gets to the end of the string, it is either in an accept or reject state. It then reports the result.
A DFA is always a linear time algorithm with linear memory usage.
The name DFA comes from these features.
Deterministic for every event, there exists only one possible outcome.
Finite there are a finite number of states and symbols the machine can handle.
Automaton a self-operating machine
A mechanical watch or self playing piano could be modeled by a DFA.