Encoding Problems
Before we can define mathematical computation models(like Turing machines) that correspond to machines, we need a way to encode these problems.
We can observe that an instance of any problem can always be encoded by a sequence of 0s and 1s. Rather, we can use a combination of symbols to encode a problem.
- The finite set of symbols and characters used for encoding is called the alphabet $\Sigma$. For example, $\Sigma = {0, 1}$.
- A string $w$ over an alphabet $\Sigma$ is a finite sequence of those symbols.
- $\Sigma^*$ Represents the set of all strings over $\Sigma$.
- A language represents a particular set of strings over an alphabet.
Operations Over Strings
Many operations can be performed on strings to modify them:
- Given strings $u$ and $v$, $u.v$ denotes their concatenation.
- A string $u$ is a prefix of string $w$ if there exists a string $v$ such that $w = u.v$.
- A string $u$ is a suffix of string $w$ if there exists a string $v$ such that $w = v.u$.
- A string $u$ is a substring of string $w$ if there exists a string $v$ and $v’$ such that $w = v.u.v’$.
Finite State Automata
Automaton $M$ has a finite number of states. It begins with an initial state, and based on the symbol currently being processed.
Let’s construct an automaton for the language $A = { w$ | $w$ contains an even number of a’s$}$, where $\Sigma = {a, b}$.
Let us define two states, $q_1, q_2$. Start with the initial state, $q_1$. On a given character, if it is $a$, we transition from $q_1 \to q_2$, or $q_2 \to q_1$. Otherwise, we stay in the current state.
If by the end of the string, we are in state $q_1$, then $w$ has an even number of a’s and belongs in $A$. This type of machine is called a deterministic finite automaton, or DFA.
The transitions of this state is represented by a transition function $\delta$. If $M$ reads the symbol $x$ on current state $y$, then the next state will be $\delta(y, x)$.
A language $A$ is called a regular language if it can be solved by a DFA.