Return to Answer

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used:

1. The pumping lemma, as exemplified in Dave's answer;
2. Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
3. A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure properties, the technique is to combine $L$ with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, e.g., the archetypical language $I= \{ a^n b^n | n \in \mathbb{N} \}$. For instance, let $L= \{a^p b^q | p \neq q \}$. Assume $L$ is regular, as regular languages are closed under complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular. For $p \geq 0 $, $I/a^p= \{ a^{r}b^rb^p| r \in \mathbb{N} \}=I.\{b^p\}$. All classes are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used:

1. The pumping lemma, as exemplified in Dave's answer;
2. Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
3. A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure properties, the technique is to combine $L$ with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, e.g., the archetypical language $I= \{ a^n b^n \mid n \in \mathbb{N} \}$. For instance, let $L= \{a^p b^q \mid p \neq q \}$. Assume $L$ is regular, as regular languages are closed under complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular. For $p \geq 0 $, $I/a^p= \{ a^{r}b^rb^p\mid r \in \mathbb{N} \}=I.\{b^p\}$. All classes are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used:

1. The pumping lemma, as exemplified in Dave's answer;
2. Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
3. A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure properties, the technique is to combine $L$ with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, e.g., the archetypical language $I= \{ a^n b^n | n \in \mathbb{N} \}$. For instance, let $L= \{a^p b^q | p \neq q \}$. Assume $L$ is regular, as regular languages are closed under complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular. For $p \geq 0 $, $I/a^p= \{ a^{r}b^rb^p| r \in \mathbb{N} \}=I.\{b^p\}$. All classes are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used:

1. The pumping lemma, as exemplified in Dave's answer;
2. Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
3. A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure properties, the technique is to combine $L$ with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, e.g., the archetypical language $I= \{ a^n b^n | n \in \mathbb{N} \}$. For instance, let $L= \{a^p b^q | p \neq q \}$. Assume $L$ is regular, as regular languages are closed under complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular. For $p \geq 0 $, $I/a^p= \{ a^{r}b^rb^p| r \in \mathbb{N} \}=I.\{b^p\}$. All classes are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.

Proof by contrapositive is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used:

1. The pumping lemma, as exemplified in Dave's answer;
2. Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
3. A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure property, the technique is to combine $L$ with regular language in order to obtain a languages known to be not regular, e.g., the archetypical language $I= \{ a^n b^n | n \in \mathbb{N} \}$. For instance, let $L= \{a^p b^q | p \neq q \}$. Assume $L$ is regular, regular languages are closed by complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular. For $p \geq 0 $, $I/a^p= \{ a^{r}b^rb^p| r \in \mathbb{N} \}=I.\{b^p\}$. All class are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used:

1. The pumping lemma, as exemplified in Dave's answer;
2. Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
3. A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure properties, the technique is to combine $L$ with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, e.g., the archetypical language $I= \{ a^n b^n | n \in \mathbb{N} \}$. For instance, let $L= \{a^p b^q | p \neq q \}$. Assume $L$ is regular, as regular languages are closed under complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular. For $p \geq 0 $, $I/a^p= \{ a^{r}b^rb^p| r \in \mathbb{N} \}=I.\{b^p\}$. All classes are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.