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

We'll now show that pushdown automata and context-free grammars describe the same class of languages. Just like regular expressions and finite automata, we can construct one from the other in a way that preserves the language in question. One way is trivial, and the other is very involved. We'll start with the easier way first.

# From CFG to PDA

A nondeterministic pushdown automaton can easily simulate the rules of CFG as follows:

1. The PDA has two states: a nonaccepting start state and a second, final state. 
2. Place a single transition from the start state to the final state that simply pushes the CFG’s start variable on the stack.
3. For every grammar rule $v\to r$, where $v$ is a variable in the grammar and $r$ is $v$'s replacement, place a self-loop transition on the final state that consumes no input, pops $v$, and pushes $r$—that is, the transition $\lambda,v\to r$.
4. For every terminal symbol, $c$, in the alphabet, $\Sigma$, add a self-loop transition on the final state that reads and pops $c$—that is, the transition $c,c\to \lambda$.

The grammar for the language $L_{eq}=\{w\;|\;w\in (a+b)^* \wedge n_a(w)=n_b(w)\}$, is given as: 

S \rightarrow SS \:|\:aSb\:|\:bSa\:|\: \lambda

We'll illustrate the process by creating a PDA for the grammar for the language $L_{eq}$:

This PDA processes a string by applying the transitions corresponding to the rules used in that example. Whenever a symbol of the alphabet is on the top of the stack, there will be a symbol in the input to match if the input string is valid and we have applied the rules correctly, at which point we apply the rule that reads and pops that symbol. The table below processes the string, $baaabb$, from the language $L_{eq}$.


| **State**  | **Input**      | **Stack**      | **Transition to Apply Next** |
|--------|------------|------------|--------------------------|
| $q_0$  | $baaabb$   | $\lambda$  | $\lambda,\lambda\to S$   |
| $q_1$  | $baaabb$   | $S$        | $\lambda,S\to SS$        |
| $q_1$  | $baaabb$   | $SS$       | $\lambda,S\to bSa$       |
| $q_1$  | $baaabb$   | $bSaS$     | $b,b\to \lambda$         |
| $q_1$  | $aaabb$    | $SaS$      | $\lambda,S\to \lambda$   |
| $q_1$  | $aaabb$    | $aS$       | $a,a\to \lambda$         |
| $q_1$  | $aabb$     | $S$        | $\lambda,S\to aSb$       |
| $q_1$  | $aabb$     | $aSb$      | $a,a\to \lambda$         |
| $q_1$  | $abb$      | $aSbb$     | $a,a\to \lambda$         |
| $q_1$  | $bb$       | $Sbb$      | $\lambda,S\to \lambda$   |
| $q_1$  | $bb$       | $bb$       | $b,b\to \lambda$         |
| $q_1$  | $b$        | $b$        | $b,b\to \lambda$         |
| $q_1$  | $\lambda$  | $\lambda$  | (accept)                 |

## Example: Grammar for palindromes

The grammar for palindromes is:

Learn how to convert a context-free grammar to a PDA and a special case of conversion of a PDA to a CFG.

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

Equivalence of PDAs and CFGs