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 look at a few examples of pushdown automata that accept the following languages:
* $L = \{wcw^R\;|\;w \in (a+b)^*\}$
* $M = \{ww^R\;|\;w \in (a+b)^*\}$
* $N = \{ a^m b^n \:|\: m <= n <= 2m \}$
* $P = \{n_a(w) = n_b(w) \:|\: w \in (a+b)^* \}$
* $Q = \{n_b(w) = 2n_a(w)\:|\: w \in (a+b)^* \}$
* $R = \{ a^i b^j c^k \:|\: i=j \vee i=k \}$
* $S = \{ a^ib^j \;|\; i \neq j \}$
#
## PDA for palindromes

The following PDA accepts the language $L = \{wcw^R\;|\;w \in (a+b)^*\}$, i.e., odd-length palindromes of $a$'s and $b$'s with a $c$ in the middle.



We push distinct symbols for $a$'s and $b$'s. Once the $c$ is consumed, we expect to find the reversal of the first half of the string in terms of $X$'s and $Y$'s. The minimal string $c$ is accepted, since it does not modify the stack (leaving it empty), and ends in an accepting state.

All the examples so far have been deterministic PDAs—there is no ambiguity as to which transition applies for each input symbol. It is not possible, however, to construct a deterministic PDA (a DPDA) for the language of even-length palindromes, i.e., $M = \{ww^R\;|\;w \in (a+b)^*\}$, since there is no symbol present to mark the middle of the string, and therefore no deterministic way to instruct the machine to move from state $q_0$ to state $q_1$. The following PDA accepts the language $M$.

Learn about pushdown automata using some examples.

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

Examples of PDA