Chomsky Hierarchy and Pumping Lemma for Context-Free Languages

A Hierarchy of Languages

• Studied regular and context-free languages in some detail. 

• All regular languages are also context-free languages, but some context-free languages are not regular. 

• We can therefore construct a containment hierarchy of these languages. 

• Languages at each level are a strict subset of the languages at the next level.

The Universe of Languages

• The universe of languages:

The Chomsky Hierarchy

Chomsky hierarchy - containment hierarchy for languages that includes the two families of languages we have studied, but also goes beyond them.

Containment of Language Classes

• The containment of Language Classes

  

Other Classes of Language

• In addition to the languages of the Chomsky hierarchy, we have met several others during the course:

  • Finite languages

  • Infinite languages

  • Inherently ambiguous languages

  • Languages accepted by DPA by final state

  • Languages accepted by a DPA by empty stack

  • Languages with an s-grammar

Relationship between Language Classes

• Relationship between language classes

  

Type - 0 Languages

• We have been primarily interested in simple language classes and their applications in relatively constrained problems. 

• At Type-0 we can become more interested in asking what computations can be done by any computational device.

Turing Machines

• A Turing machine is an automaton like those we have studied, but with an infinitely long ‘tape’ that it can read and write to. 

• A linear-bounded automaton is essentially the same but the tape has a fixed finite length.

Computability

• Turing machines help computer scientists to understand the limits of computation. 

• Church-Turing Thesis - everything computable is computable by a Turing machine. 

• But if this is the case, how do Turing machines

  • Compute algorithmic expressions?

  • Execute stored programs?

  • . . .

Incomputable Problems

• There are problems for which one cannot create a Turing machine (nor a Java program, C program, . . . ) that will always halt with a ‘yes’ or ‘no’ answer. 

  • Halting problem

  • Post correspondence problem 

  • . . .

What do we want from a Programming Language?

• Expressiveness 

  • Most natural languages are context-free - but if we want to have matching brackets (or nested begin-end, for-next, etc. statements) then need a more powerful language than a regular one. 

• Clarity 

  • The meaning of a program has to be unambiguous. Inherently ambiguous languages must therefore be avoided, and unambiguous grammars should be preferred. 

• Efficiency

  • Parsing non-deterministic languages can involve huge amounts of work having to be done in parallel or lots of backtracking. Using a deterministic language makes the understanding of the language much simpler.

Good Choices for Programming Languages

• Good choices for programming languages

  

Attaching Meaning to Programs

• In this module - interested in syntax - rules describing whether an item is in a language. 

• If the items in our languages are computer programs then we also need to associate them with semantics - what the item means. 

• One way to do this is using an attribute grammar. 

• Each production in the grammar has an associated rule stating how the meaning of the LHS symbol is made up from the meanings of the RHS symbols.

Closure Properties for Context-Free Languages

• Theorem - the family of CFLs is closed under union, concatenation and star-closure. 

• Proof outline - suppose L₁ and L₂ are CFLs with grammars G₁ = (V₁, T₁, S₁, P₁) and G₂ = (V₂, T₂, S₂, P₂).

Intersection and Complementation for CFLs

• Intersection and Complementation for CFLs

  

Pumping Lemma for Context-Free Languages

• We previously looked at how Pumping Lemma for Regular Languages encapsulated a result about regular languages, and could be used to show that a language was not regular. 

• Look at a similar result for CFLs. This time, it says that, in any sufficiently-long string in a CFL, we can find two substrings that can be pumped (repeated as often as desired), and the result remains in the language. Again, we can use this Pumping Lemma to show that a language is not context-free.

  

Proof Outline

Proof outline:

Template for Application of PL for CFLs

Template for Application of PL for CFGs