Close
Register
Close Window

CS4114 Formal Languages and Automata: Spring 2022

Chapter 8 Properties of Context-free Languages

Show Source |    | About   «  7.4. Deterministic Pushdown Automata   ::   Contents   ::   9.1. Turing Machines  »

8.1. Properties of Context-Free Languages

8.1.1. Introduction

We now have a lot of evidence that there are languages that are not in the class of CFLs. So, we want ways to be able to tell the difference. When we studied regular languages, we developed two tools to help us tell if a language is regular or not. One was closure properties on regular languages, that could help us both to prove in some cases that a language is regular, and could help us to prove in other cases that a language is not regular.

In a similar way, there exist closure properties for CFLs, and so we can use these properties in appropriate cases both to prove a language is a CFL, and also prove that other languages are not CFL.

We used a pumping lemma for regular languages to prove that certain languages are not regular (because they could not be pumped). Likewise, we will see that there is a pumping lemma for CFLs (though it is somewhat different from the pumping lemma for regular languages), and that it can be used to prove that certain languages are not a CFL.

8.1.2. Closure Properties for Context-Free Languages

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

8.1.3. Proving a language is not CFL - Using a Pumping Lemma

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

8.1.4. Pumping Lemma Example 1

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

8.1.5. Pumping Lemma Example 2

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

8.1.6. Pumping Lemma Example 3

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

8.1.7. Pumping Lemma Example 4

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

8.1.8. Pumping Lemma Example 5

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

   «  7.4. Deterministic Pushdown Automata   ::   Contents   ::   9.1. Turing Machines  »

nsf
Close Window