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

Let's consider the following PDA, which accepts the language $L = \{n_b(w) = n_a(w) + 1\mid w \in (a+b)^*\}$.

In the diagram above, we initiated the stack with an $X$, which effectively increments the count of $b$’s in a string accepted by the PDA. Using such a stack "start symbol" can be helpful for other purposes as well. 

The following PDA for $L_{eq} = \{n_a(w) = n_b(w) \:|\: w \in (a+b)^* \}$ uses a start symbol, $S$, to know when the stack has "hit bottom" (i.e., when $S$ is at the top of the stack, it is the *only* symbol on the stack). Furthermore, whenever an $S$ is on the top of the stack in this machine, it means that an equal number of $a$’s and $b$’s have been encountered so far up to that point.

Compare the transitions in state $q_1$ above with those from the first figure for language $L$. The following transitions have replaced $a,\lambda\to X$ from the PDA for the language $L$:

\begin{align*}
a,S & \to XS \\
a,X & \to XX
\end{align*}

Since $S$ is always on the bottom of the stack in this machine, we know that when it is at the top of the stack, nothing else is on the stack, so we can push an $X$ to account for the symbol $a$ just read. The transition $a,Y \to XY$ is omitted because, like before, $X$'s and $Y$'s do not appear on the stack simultaneously in this PDA. The two replacement transitions mentioned above are equivalent to $a,\lambda\to X$ in that their net effect is to add an $X$ to the stack when reading an $a$.

In like fashion, we replaced the rule $b,\lambda\to Y$ from the first figure with the following two transitions in the figure above, because their net effect is to push a $Y$ when a $b$ is read:


Learn about the formal definition of deterministic PDA.

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

Pushdown Automata and Determinism