The reversal of a string $w = a_1 a_2 \cdots a_n$ is the string with the symbols written in reverse order, $w^R = a_n \cdots a_2 a_1$. Formally,
If $w = w^R$, we say $w$ is a palindrome
That strings can be reversed is a consequence of the fact that concatenation is not commutative.
$(xy)^R = y^R x^R$.
We will show this by induction on $x$.
For our base case, let $x = \varepsilon$. We have \begin{align*} (xy)^R &= (\varepsilon y)^R &\text{substitution}\\ &= y^R &\text{definition of $\varepsilon$} \\ &= y^R \varepsilon &\text{definition of $\varepsilon$}\\ &= y^R \varepsilon^R &\text{definition of reversal}\\ &= y^R x^R & \text{substitution} \end{align*}
Now, for our induction step, let $x = az$ for some word $z \in \Sigma^*$ and assume that $(zy)^R = y^R z^R$. Then we have \begin{align*} (xy)^R &= ((az)y)^R &\text{subtitution}\\ &= (a(zy))^R &\text{definition of concatenation}\\ &= (zy)^R a &\text{definition of reversal}\\ &= (y^R z^R) a &\text{inductive hypothesis}\\ &= y^R (z^R a) &\text{associativity}\\ &= y^R (az)^R &\text{definition of reversal}\\ &= y^R x^R &\text{subtitution} \end{align*}
Informally, languages are just sets of strings and we describe a language in the same way as for any other set.
Here are some examples of languages.
We can define the notion of a language more formally, with respect to an alphabet $\Sigma$.
We denote by $\Sigma^*$ the set of all finite words over $\Sigma$. A language over $\Sigma$ is a subset of $\Sigma^*$.
You might notice that the more curious definition is for $\Sigma^*$. If you recall our brief diversion about monoids, you might recognize that $\Sigma^*$ is really just the free monoid on $\Sigma$.
Since languages are sets, we can perform any set theoretic operations we're familiar with, like union and intersection.
For a language $L \subseteq \Sigma^*$, the complement of $L$ is $\overline L = \Sigma^* \setminus L$.
This also means there are a few things we have to be careful with. For example, there is the notion of the empty language $\emptyset$, which is the language with no strings in it. This is different from the language $\{\varepsilon\}$, which is the language containing the empty string.
We can also extend many operations on strings to operations on languages.
For two languages $L_1$ and $L_2$, we define the catenation of $L_1$ and $L_2$ by $$ L_1 L_2 = \{uv \mid u \in L_1, v \in L_2 \}.$$
This allows us to define powers for languages.
For a language $L \subseteq \Sigma^*$, the $k$th power of $L$ is
This definition leads to an interesting operation.
The Kleene star or Kleene closure of $L$ is defined by $$ L^* = \bigcup_{i \geq 0} L^i.$$ We can similarly define the positive Kleene closure of $L$ by $$ L^+ = \bigcup_{i \geq 1} L^i.$$
Let $\Sigma = \{a,b,c\}$. Then $L = \{ab, bc\}$ is a language over $\Sigma$. If we take the Kleene star of $L$, we get the language made of up of combinations of $ab$ and $bc$, like $ababbcabbcbcab$.
One use of this is for constructing codes. In formal language theory, a code over an alphabet $\Sigma$ is a language $K \subseteq \Sigma^+$ such that if $w \in K^+$ then $w$ has a unique factorization into words of $K$ (here is a use of "factor" as "subword"). It's not hard to see that not every language is a code.
Finite automata are arguably the simplest model of computation. Finite automata first appeared as far back as the 1940s in the context of early neural networks. The idea was that we wanted to represent an organism or robot of some kind responding to some stimulus, which we can also call events. Upon the occurrence of an event, the robot would change its internal state in response and there would be a finite number of possible such states. Today, the use of finite automata for modelling such systems is still around in a branch of control theory in engineering under the name discrete event systems. But all of this has nothing to do with how we're going to consider finite automata.
First, we'll introduce the idea of a "machine" as used in the theory of computation, which we'll be coming back to throughout the course. A machine has an input tape, divided into cells, with an input word written on it. The machine has a tape head that can scan the input tape, reading a symbol from each cell.
The machine also contains a number of states, and depending on the symbol that is read by the tape head, the machine's internal state will change. Upon reading the entire input, the machine accepts or rejects the input word based on the state that the machine is in. We call these finite automata because they have only a finite number of states. It wasn't stated explicitly, but based on the description, we also assume that the tape head can only move in one direction. Because of this restriction, it's not really necessary to think about the tape portion of the machine, at least for now.
We can represent finite automata by drawing the important part of the machine: the state diagram. We draw each state as a circle and label it as appropriate. Transitions are represented as arrows, leaving one state and entering another, labelled by the appropriate input symbol. We denote accepting states by a double circle and we denote the start state by an arrow that comes in from nowhere in particular.
We will give a formal definition for finite automata.
A deterministic finite automaton (DFA) is defined as a 5-tuple $A = (Q,\Sigma,\delta,q_0,F)$, where
Note that by our definition, $\delta$ must be defined for every state and input symbol. We call this a deterministic finite automaton because the transition function $\delta$ is uniquely determined by the state and input symbol.