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

#
## Examples of nonregular languages
We'll use the pumping theorem to prove that the following languages are not regular:
* The language $L_{ab}=a^nb^n$.
* The language of palindromes.
* The language of repeated halves, $\{ww \;|\; w \in (a+b)^*\}$.
* The language over $\Sigma=\{(,)\}$ of balanced parentheses.
* The language $\{a^mb^n \;|\; m > n\}$.
* The language PRIME = $\{a^n\}$, where $n$ is a *prime number*.
* The language $\{a^{n^2} \;|\; n>0\}$.

### The language $L_{ab}$

We'll now show that the language $L_{ab}=a^nb^n$ is not regular by showing that it does not satisfy the pumping theorem.

Intuitively, we can surmise that $L_{ab}$ is not regular because a finite machine has no way to track an arbitrarily large number of $a$'s to match the subsequent $b$'s. We can only go so far before we run out of states. Consider the diagram below accepting the singleton language $\{ab\}$. (Once again, we omit the jail state for readability.)



Now, how can we define a machine to accept $\{ab,aabb\}$? Or $\{ab,aabb,aaabbb\}$? We need to add more states. See the animation below.


A machine with a finite number of states will never have enough states to match an arbitrarily large number of symbols.

The reasoning above satisfies our intuition, but it is *not a proof*! If $L_{ab}=a^nb^n$ were regular, then per the pumping theorem, we could pick *any string* in this language of at least $p$ symbols in length, and partition it into three concatenated substrings, $xyz$, and then pump $y$ however much we require and still obtain a string in the language. This is how infinite regular languages behave. We'll choose the string $a^pb^p$, which is more than long enough for us to invoke the pumping theorem and show that it cannot be partitioned this way.

If $L_{ab}$ were regular, then, using the pumping theorem, we could partition $a^pb^p$ into three parts, $xyz$. Since the condition $|xy| \leq p$ must hold, we know that the substring $y$ must occur somewhere within the first $p$ symbols of $a^pb^p$, which means that it occurs somewhere within the initial run of $a$’s in this string (it doesn’t matter exactly where or how long it is; all we know is that it is no longer than $p$). It suffices to say that in our case, $y$ consists of nothing but $a$’s, because there are $p$ $a$’s to begin with. Now, what happens when we try to pump $y$? The number of $a$’s in the string changes, but the number of $b$’s does not. This causes the pumped string to “fall out” of the language—it no longer has an equal number of $a$’s and $b$’s. This violates the pumping theorem (this language doesn’t “pump”), so we conclude that  $L_{ab}$ is not regular. (That was easy!)

> **Remember:** A cycle must occur within the processing of the first $p$ input symbols of any string in a regular language.


The key to handily solving this problem was how we chose the test string. The pumping theorem applies to *any* string at least $p$ symbols long because such a string forces a cycle when processing the first $p$ symbols in an accepting path in the automaton. We chose a string that allowed us to use the condition $|xy| \leq p$ to our advantage. However, it wasn’t necessary to do this for this language. Suppose we chose a string $a^kb^k$, where $2k \geq p$, but $k$ is not necessarily greater than or equal to $p$. In this case, the condition $|xy| \leq p$ would serve no useful purpose (because $y$ could have $a$’s and/or $b$’s), but we could still consider all the ways in which $y$ might appear:

1. If $y$ appears wholly within the initial run of $a$’s, then we conclude, as before, that the number of $a$’s changes, but the number of $b$’s does not, violating the pumping theorem (the number of $a$’s no longer equals the number of $b$’s).

2. If instead, $y$ straddles the boundary between the $a$’s and $b$’s, then it is of the form $a^ib^j$, so we have $a^kb^k=a^{k-i}a^ib^jb^{k-j}$.  Pumping $y$ yields a string that is no longer a single run of $a$’s followed by a single run of $b$’s. For example, the string $xy^2z$ is $a^{k-i}(a^ib^j)(a^ib^j)b^{k-j}$ (parentheses shown to emphasize $y^2$), which has *four runs* of characters: $a^kb^ja^ib^k \notin L_{ab}$. Again, pumping fails.

3. The only other possibility is that $y$ occurs wholly inside the run of $b$’s, which is analogous to case 1 above. Pumping, in this case, changes the number of $b$’s without changing the number of $a$’s, again falling out of the language $L_{ab}$.

So, without using the condition $|xy| \leq p$, we have to consider all possible cases of how $y$ can appear in the string to show that there is no partition whatsoever that satisfies the pumping theorem. The second and third steps above became unnecessary when we used the string $a^pb^p$ along with the condition $|xy| \leq p$.  It is a good idea to use this condition of the pumping theorem whenever it applies (which is often). 

We _*cannot assign a fixed, numerical length*_ to $x$, $y$, or $z$, nor say precisely which positions the partitions occupy in the string. All we may assume are the conditions of the pumping theorem, which are in terms of the parameter $p$, and we must show that no valid choice for $y$ satisfies the pumping theorem. It is _*always erroneous*_ to say, for example, "assume that $|y|=2$", etc. (the same goes for $x$ and $z$).

> **Note:** We can *only assume* that $|xy| \leq p$ (and therefore, $|y| \leq p$) and that $y$ must appear within the leading $p$ symbols of a string to be pumped.

### A language of palindromes

A **palindrome** is a string that reads the same backward and forward, like "radar" or "madam." The language of palindromes over $\Sigma=\{a,b\}$ is not regular. Once again, our intuition tells us that we need an infinite number of states to check for matching symbols on either end of an arbitrarily large string. To prove that the language is not regular, we need to show that it doesn’t "pump." To make the process as easy as possible, we pick a palindrome that has the same symbol occupying the first $p$ symbols in the string, such as $a^pba^p$, and equate it to the expression $xyz$. The requirement $|xy| \leq p$ implies that the substring $y$ must appear within the first $p$ symbols, which are all $a$’s. But this means that when we pump $y$ $i$-times, say, we get a string of the form $a^{p+i|y|}ba^p$, where the number of $a$’s before the $b$ has changed, but the number of $a$’s after the $b$ hasn’t, it results in a *nonpalindrome*. This violates the requirements of the pumping theorem for regular languages, so we conclude that this language is not regular.



### The language of repeated halves

The language of repeated halves, $\{ww \;|\; w \in (a+b)^*\}$, is not regular. An example of a string in this language is $a^pba^pb$. The same logic from the previous example applies here. The substring $y$ must occur within the initial run of $a$’s. When it is pumped, the number of initial $a$’s changes, but nothing else does, giving a string of the form $a^{p+i|y|}ba^pb$, which is *not* the concatenation of two equal substrings. So the pumping has failed.



### The language of balanced parentheses

The language over $\Sigma=\{(,)\}$ of balanced parentheses, with strings such as $(( )(( )))$, is not regular. If it were, then we could pump the string $(^p)^p$. But, once again, the fact that $|xy| \leq p$ means that $y$ consists of only left parentheses, which, when pumped, destroys the balance.

With simple examples like these, one might get the idea that it is always easy to show that a language is nonregular. Let's examine three more languages that present increasing levels of difficulty in proving them nonregular.

### The language of a’s followed by fewer b’s

The language $\{a^mb^n \;|\; m > n\}$, meaning that there are always more $a$’s than $b$’s, is not regular. If it were, then we could pump the string $a^{p+1}b^p$. This time, we take advantage of the Kleene star in the condition $xy^*z \in L$ from the pumping theorem by using the *zero-repetitions* case. We know that $y$ must occur within the run of $a$’s. When we *pump down* once (i.e., ignoring the cycle that defines $y$), we obtain the string $a^{p−|y|+1}b^p$, making the number of $a$’s less than or equal to the number of $b$’s—another pumping fail. Pumping “up,” in this case, would not accomplish anything.



> **Note:** For some languages, we need to *pump down* once to show a language doesn't satisfy the pumping theorem.

### The language PRIME

The language PRIME = $\{a^n\}$, where $n$ is a prime number, is not regular. The alphabet here is the singleton $\Sigma=\{a\}$. Let’s consider the string $a^k$ where $k \geq p$ and $k$ is prime. Our goal is to pump $y$ up a certain number of times which will guarantee that the resulting string is a *composite number* instead of a prime. The only fixed quantity we have is $k$, so we'll pump $y$ $k$-times, getting the string $xy^{k+1}z$. Since the string consists only of $a$’s, we can rearrange the previous expression as $xyzy^k$ by moving all but one of the $y$'s to the right. Recalling that $|xyz|=k$, we have: 

Learn to use the pumping theorem to prove a language is nonregular.

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

Nonregular Languages

Examples of nonregular languages