Close
Close Window

CS4114 Formal Languages Spring 2021

Chapter 5 Identifying Non-regular Languages

Show Source |    | About   «  4.7. Closure Properties of Regular Grammars   ::   Contents   ::   6.1. Context-Free Languages  »

5.1. Identifying Non-regular Languages

5.1.1. Identifying Non-regular Languages

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.2. Proving that a languages is not regular

1 / 13 Settings
<<<>>>

Our next step is to come up with a more formal proof that $L_2 = \{a^nb^n | n > 0 \}$ is nonregular. We are going to do this using a Proof by Contradiction. So of course, the first step is to assume that $L_2$ is regular, and show that this assumption causes a contradition.

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

5.1.3. The Concept of Pumping

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.4. Pumping Lemma

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.5. Pumping Lemma Example 1

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.6. Pumping Lemma Example 2

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.7. Pumping Lemma Example 3

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.8. Pumping Lemma Example 4

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.9. Pumping Lemma Example 5

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.10. Pumping Lemma Example 6

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.11. Use Closure Properties to prove L is not regular

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.12. Use Closure Properties to prove L is not regular: Example 1

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.13. Use Closure Properties to prove L is not regular: Example 2

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.14. Use Closure Properties to prove L is not regular: Example 3

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.15. Adversary game

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.1.16. Adversary game examples

   «  4.7. Closure Properties of Regular Grammars   ::   Contents   ::   6.1. Context-Free Languages  »

nsf
Close Window