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

# Proving languages are not regular using closure properties
Using our knowledge of a few nonregular languages, we can conclude that other languages are nonregular merely by using the closure properties of regular languages. For example, the language NOTPRIME ($\{a^n\}$ where $n$ is *not* prime) is not regular. If it were, then its complement, PRIME ($\{a^n\}$ where $n$ *is* prime), would also be, but we know that PRIME is *not* regular, so NOTPRIME can’t be regular since regular languages are closed under complement. 

It is fruitless to attempt to use the pumping theorem on a language like this, defined with a negative (e.g., using "not"). Instead, we show its complement is not regular. Depending on the language, other closure properties can be used to show that a language is not regular.

We can also show that the language EQUAL, defined as $\{n_a(w)=n_b(w)\;|\;w \in (a+b)^*\}$ (i.e., strings where the number of $a$’s and $b$’s are equal, but the letters can appear in any order), is not regular by applying the pumping theorem to the string $a^pb^p$ (remember, we can choose *any* qualifying string in the language). But we can use the closure properties of regular languages to avoid having to use the pumping theorem. Consider the set of strings formed by the intersection EQUAL $\cap \; a^*b^*$. This is the set of strings of $a$’s and $b$’s where the number of each letter is equal, but also where the $a$’s must precede the $b$’s. But this is also the language $L_{ab}=a^nb^n$, which we already know is *not* regular. Since $a^*b^*$ represents a regular language, then EQUAL must not be regular because regular languages are closed under intersection.


The language $L_{ne}=\{a^m b^n \;|\; m \neq n\}$ is not regular (notice the $\neq$, which implies a "not"). Since we don't get to choose the size of $y$, it is possible that pumping $y$ will leave the number of $a$’s unequal to the number of $b$’s. In general, we can't prove a negative with any theorem directly. This language is *not the complement* of $L_{ab}=\{a^nb^n\}$, by the way, because $\overline{L_{ab}}$ also includes strings that aren't necessarily a run of $a$’s followed by a run of $b$’s, no matter the number of occurrences of each character (strings like $bbaa$, as well as strings like $baa$, and $abab$). However, $L_{ne}$ *does* include all the strings in $\overline{L_{ab}}$, which are run of $a$’s followed by a run of $b$’s, so we can compute the following difference:



Learn how to use closure properties to show that a language is not regular.

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

Using Closure Properties to Show Nonregularity

Proving languages are not regular using closure properties