6.1. Context-Free Grammars Part 1¶
6.1.1. Context-Free Languages¶
In previous chapters, we saw that some languages are regular languages, which means that we can define a DFA, NFA, regular expression, or regular grammar for them. We also discussed using closure operators to show that other languages are regular if they can be derived from known regular languages using operators known to be closed for regular languages. Examples of regular languages:
keywords in a programming language
names of identifiers
integers
a finite list of miscillaneous symbols such as = \ ;
Then we discussed ways to prove that a language is non-regular, such as using the Pumping Lemma or using operators known to be closed for regular language to derive a known non-regular language. Exxamples of non-regular languages include:
\(\{a^ncb^n | n > 0\}\)
expressions: \(((a + b) - c)\)
block structures (\(\{\}\) in Java/C++ and
begin…endin Pascal)Balanced parentheses
We know that not all languages are not regular, since we’ve proved that some are not.
(Something to think about: If you were to write a program in your favorite programming language to recognize any of those languages, what is the minimum memory that you need for each?)
Now we will look at a class of languages that is larger than the class of regular languages, context-free languages. And we will discuss ways to represent them.
