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 … end in 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.

1 / 14 Settings

<<<>>>

Definition: A grammar $G=(V,T,S,P)$ is context-free if all productions are of the form
$A \rightarrow x$
where $A \in V$ and $x \in (V∪T)^∗$.
(T includes $\lambda$.)

Saving...
Server Error
Resubmit

6.1.2. String Derivation¶

1 / 38 Settings

<<<>>>

Given a grammar $G$, the most important question to ask is whether a given string $w$ can be derived from $G$. This process is called string derivation.

String derivation begins with the start variable for the grammar (we often use $S$ as the start variable). A series of replacements on variables is performed until there are no more variables to replace. At each step, a variable is replaced by the right hand side of some production rule that has that variable as its left hand side. The goal is to select the proper replacement steps that will lead to $w$.

Saving...
Server Error
Resubmit

6.1.3. Derivation Trees¶

1 / 13 Settings

<<<>>>

We have covered how to derive a string by using sentential forms. Now we a more visual derivation method.

Derivation Trees (also known as parse trees) represent a derivation, but do not show the order in which the productions were applied.

...

$A$

$a_1$

$a_2$

$a_3$

$a_n$

A

A

a

a

B

c

$\lambda$

$\lambda$

Saving...
Server Error
Resubmit

6.1.4. Derivation Trees Example¶

1 / 7 Settings

<<<>>>

Here is an example that shows how can we build a parse tree for the string $aacbb$ for the given grammar.

1. S
2. →
3. AcB

1. A
2. →
3. aAa

1. A
2. →
3. λ

1. B
2. →
3. Bbb

1. B
2. →
3. λ

2. →

A

c

B

B

b

b

λ

a

A

a

λ

Saving...
Server Error
Resubmit

6.1.5. Practice question 1¶

6.1.6. Membership Problem¶

1 / 24 Settings

<<<>>>

The most important question that we can ask about a grammar is whether a given string can be derived from it. This is know as the Membership Problem.

Saving...
Server Error
Resubmit

6.1.7. Practice question 2¶