37.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 that recognizes that language, or we can represent it with a regular expression or regular grammar. Here are a few examples of regular languages:

• keywords in a programming language

• names of identifiers

• integers

• a finite list of miscillaneous symbols such as $=$.

We also know that some languages are non-regular, and we learned how to use tools like the Pumping Lemma to prove a given language is non-regular. Examples of non-regular languages include:

• $\{a^ncb^n\ |\ n > 0\}$

• mathematical expressions like $((a + b) - c)$

• block structures for programming languages ($\{\}$ in Java/C++ and begin … end in Pascal)

• Balanced parentheses

Now we will look at a class of languages that is larger than the class of regular languages, called context-free languages or CFG. Perhaps not surprisingly, a CFL is any language that can be represented by a context-free grammar or CFG.

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

37.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

37.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

37.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

37.1.5. Practice question 1¶

37.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

37.1.7. Practice question 2¶