Search⌘ K
AI Features
Home
Courses
Theory of Computation

Nonregular Languages

Explore the concept of nonregular languages and how to apply the pumping theorem to prove languages like a^n b^n, palindromes, and balanced parentheses are not regular. Learn to analyze language structures and understand why finite automata cannot recognize these complex patterns.

We'll cover the following...

Examples of nonregular languages

We’ll use the pumping theorem to prove that the following languages are not regular:

  • The language Lab=anbnL_{ab}=a^nb^n.
  • The language of palindromes.
  • The language of repeated halves, {ww  ∣  w∈(a+b)∗}\{ww \;|\; w \in (a+b)^*\}.
  • The language over Σ={(,)}\Sigma=\{(,)\} of balanced parentheses.
  • The language {ambn  ∣  m>n}\{a^mb^n \;|\; m > n\}.
  • The language PRIME = {an}\{a^n\}
...