Gain insights into formal languages, regular languages, regular expressions, context-free languages, and Turing machines. Delve into automata models and enhance problem-solving skills through extensive exercises.

What are the mathematics behind computers? What are the theoretical foundations of computer languages? Such questions can be explored by understanding formal languages and automata models. 

In this comprehensive course, you’ll explore formal languages, regular languages, and how to model them with their associated automata models. Next, you’ll cover regular expressions and grammar, and their equivalents. Then, you’ll explore context-free languages (the foundations of programming languages), pushdown automata, and the relationship between them. Toward the end, you’ll learn about recursively enumerable languages, Turing machines with their variations, context-sensitive languages, and unrestricted grammars.

By the end of the course, you’ll have gained a deep understanding of several formal languages and their associated automata. Also, since there are plenty of exercises throughout the course, your understanding and problem-solving skills will be thoroughly reinforced.

Theory of Computation


# Formal definition
The automata we have discussed so far are all deterministic in that there is no ambiguity about which edge to follow from each state. Deterministic finite automata are also easy to program; we simply need have a case for each state, and inside each case, we choose the target state corresponding to the current input symbol. In the next section, we'll see how nondeterministic finite automata can also be useful.

A **deterministic finite automaton** (DFA) is a finite state machine consisting of the following:
* $Q$, a set of **states**, one of which is the initial (or start) state, and a subset of which are final (or accepting) states.
* $\Sigma$, an **alphabet** of valid input symbols.
* $\delta:Q \times \Sigma \rightarrow Q$, a **transition function** which, given a state and input symbol, determines the next state of the machine.

The definition above is merely a mathematical reformulation of what we already understood a DFA to be. The transition function, $\delta$, represents the transitions/edges in the machine. The subset of $Q$ comprising the final states can be empty in the case of machines that produce an output string instead of a yes-or-no result. There must be *exactly one* transition out of every state for each symbol in the alphabet of the DFA.

> **Remember:** There can only be one transition out of every state for each symbol in the alphabet of the DFA.

# DFA accepting strings ending with $b$
To illustrate the application of the formal definition of a DFA, consider the DFA in the figure below, which accepts the language $L$ that contains all strings over the alphabet $\Sigma=\{a,b\}$ that end with the symbol $b$. We can write this language as $L = \{\textrm{All strings that end with }b\}$.

Every time we read a $b$, for all we know it could be the last symbol in the input string, so we move to the accepting state $q_1$; otherwise, we move to state $q_0$. Therefore, the formal definition for this DFA is:

* $Q=\{q_0,q_1\}$, where $q_0$ is the initial state and $\{q_1\}$ is the set of final states
* $\Sigma=\{a,b\}$
* $\delta=\{((q_0,a),q_0),((q_0,b),q_1),((q_1,a),q_0),((q_1,b),q_1)\}$

Yet another way to depict a DFA is with a transition table.

$$\text{ Transition Table for the Language } L$$

|**State**    | $\pmb{a}$    | $\pmb{b}$    |
|---------|--------|--------|
|$\pmb{q_0}$    |$q_{0}$ |$q_1$   |
|$+\pmb{q_1}$    |$q_{0}$ |$q_1$  |

In the transition table, the initial state appears first and a plus sign indicates each final state.

Since tables are a common data structure in programming languages, they offer yet another approach to implement DFAs in code. 
## Simulation of the language $L$
The program below uses Python's dictionary data type to simulate the transitions in the table above. The dictionary named `transitions` maps each `<state,symbol>` input pair to a machine state. This program is more concise than using multiple `if` and `else` statements to check states directly.


Get an introduction to the formal definition of deterministic finite automata and explore examples of different DFAs.

Getting Started

Exam on Formal Languages

Finite Automata

Exam on Finite Automata

Regular Expressions and Grammars

Exam on Regular Expressions and Grammars

Properties of Regular Languages

Exam on Properties of Regular Languages

Pushdown Automata

Exam on Pushdown Automata

Context-Free Grammars

Exam on Context-Free Grammars

Properties of Context-Free Languages

Exam on Properties of Context-Free Languages

Turing Machines

Exam on Turing Machines

The Landscape of Formal Languages

Exam on the Landscape of Formal Languages

Computability

Exam on Computability

Conclusion

Deterministic Finite Automata