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

# Converting an arbitrary PDA to CFG
To convert an arbitrary PDA to a CFG, we somehow need to relate the states and transitions of the PDA, including stack operations, to variables and rules in a CFG. This is a tall order but a doable one. To understand the algorithm, we need to take a deeper look at stack behavior in PDAs. We start with the simple, one-state PDA for $L_{eq} = \{n_a(w)\:=\:n_{b}(w)\:|\:w \in (a+b)^* \}$ found in the figure below.

While referring to this figure, let's study the following trace of $aaababbbbbaa$.


| **Step** | **Input**           | **Stack**           |
|------|-----------------|-----------------|
| 0    | $aaababbbbbaa$  | $\lambda_1$     |
| 1    | $aababbbbbaa$   | $X_1$           |
| 2    | $ababbbbbaa$    | $X_2X_1$        |
| 3    | $babbbbbaa$     | $X_3X_2X_1$     |
| 4    | $abbbbbaa$      | $X_2X_1$        |
| 5    | $bbbbbaa$       | $X_4X_2X_1$     |
| 6    | $bbbbaa$        | $X_2X_1$        |
| 7    | $bbbaa$         | $X_1$           |
| 8    | $bbaa$          | $\lambda_2$     |
| 9    | $baa$           | $Y_1$           |
| 10   | $aa$            | $Y_2Y_1$        |
| 11   | $a$             | $Y_1$           |
| 12   | $\lambda$       | $\lambda$       |

We have numbered the stack variables (and the lambdas) with subscripts according to the order in which they appear on the stack so we can inspect their stack lifetimes. As always, the stack begins and ends empty, and in between, it grows and shrinks in size repeatedly. A stack variable’s lifetime is the number of steps from when it is first pushed until it is removed from the stack. The lifetimes of the stack variables in the above table appear in the following table.

| **Stack Variable** | **Lifetime (In Steps)** | **Step Range** |
|----------------|---------------------|------------|
| $X_1$          | 7                   | 1--7       |
| $X_2$          | 5                   | 2--6       |
| $X_3$          | 1                   | 3--3       |
| $X_4$          | 1                   | 5--5       |
| $Y_1$          | 3                   | 9--11      |
| $Y_2$          | 1                   | 10--10     |


From the time the first variable, $X_1$, appears on the stack until it is removed, three other $X$’s ($X_2$, $X_3$, and $X_4$) come and go. We call these actions the aftereffects of $X_1$. The very presence of a stack variable leads to associated aftereffects, depending on which transitions subsequently execute. The second $X$ to appear on the stack, $X_2$, causes the variables $X_3$ and $X_4$ to come and go. These actions also consume input symbols. Although this PDA has only one state, that is not always the case with an arbitrary PDA. The way we relate the actions of any PDA to grammar rules is by means of the following abstraction.

>**Note:** The symbol $\langle pVq\rangle$ represents the actions of a PDA that move from state $p$, having the symbol $V$ at the top of the stack, to state $q$ after one or more transitions, such that $V$ and its aftereffects have all been popped from the stack.

In other words, $\langle pVq\rangle$ represents the one or more symbols consumed while $V$ and its aftereffects were on the stack, and we were in state $p$ when $V$ was popped. We entered state $q$ at the moment $V$ and its aftereffects were completely removed. Symbols of this form will become the variables in the resulting grammar, representing the sequence of movements in the PDA that reads a substring and pops a stack variable along with all its aftereffects, while traveling through an arbitrary number of states. In the example above, we have the following correspondences between 3-tuple symbols of the form $\langle pVq\rangle$ and movements in the machine, listed in the order in which they are removed from the stack (review the first table of this lesson). We also include the configurations starting with an empty stack (corresponding to lines 0 and 8 in the trace of $aaababbbbbaa$).

| **Symbol**                           | **PDA Action**                                                       | **String Consumed** |
|----------------------------------|------------------------------------------------------------------|-----------------|
| $\langle q_0X_3q_0\rangle$       | $(q_0,babbbbbaa,X_3X_2X_1) \vdash (q_0,abbbbbaa,X_2X_1)$         | $b$             |
| $\langle q_0X_4q_0\rangle$       | $(q_0,bbbbbaa,X_4X_2X_1) \vdash (q_0,bbbbaa,X_2X_1)$             | $b$             |
| $\langle q_0X_2q_0\rangle$       | $(q_0,ababbbbbaa,X_2X_1) \vdash ^* (q_0,bbbaa,X_1)$              | $ababb$         |
| $\langle q_0X_1q_0\rangle$       | $(q_0,aababbbbbaa,X_1) \vdash ^* (q_0,bbaa,\lambda)$             | $aababbb$       |
| $\langle q_0Y_2q_0\rangle$       | $(q_0,aa,Y_2Y_1) \vdash (q_0,a,Y_1)$                             | $a$             |
| $\langle q_0Y_1q_0\rangle$       | $(q_0,baa,Y_1) \vdash ^*(q_0,\lambda,\lambda)$                   | $babb$          |
| $\langle q_0\lambda q_0\rangle$  | $(q_0,bbaa,\lambda_2) \vdash ^* (q_0,\lambda,\lambda)$           | $bbaa$          |
| $\langle q_0\lambda q_0\rangle$  | $(q_0,aaababbbbbaa,\lambda_1) \vdash ^* (q_0,\lambda,\lambda)$   | (entire string) |

The symbol $\langle q_0X_1q_0\rangle$, for the first $X$ pushed, represents steps 1–7 in the trace in the first table, which corresponds to consuming the characters $aababbb$ as part of the aftereffects of $X_1$ (starting with the second $a$ in the original string).

The way we relate this to a grammar rule is by noticing that, starting from step 1, the transition $a,\lambda\to X$ was used to push the second $X$ ($X_2$). We can express this step of the PDA as the grammar rule:

Learn about the general 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

From PDA to CFG (General Case)

Converting an arbitrary PDA to CFG

Step	Input	Stack
0	$aaababbbbbaa$	$\lambda_1$
1	$aababbbbbaa$	$X_1$
2	$ababbbbbaa$	$X_2X_1$
3	$babbbbbaa$	$X_3X_2X_1$
4	$abbbbbaa$	$X_2X_1$
5	$bbbbbaa$	$X_4X_2X_1$
6	$bbbbaa$	$X_2X_1$
7	$bbbaa$	$X_1$
8	$bbaa$