What are Context-Free Languages?

It is a collection of languages that are associated with context-free grammars.

  • Includes all regular languages and many additional languages.

Context-Free Grammars

It is a 4-tuple where (V, $\sum$, R, S), where:

  1. V is a finite set called the variables. Is uppercase.
  2. $\sum$ is a finite set, disjoint from V, called terminals. Is lowercase.
  3. R is a finite set of rules, with each rule being a variable and a string of variables and terminals
  4. $S \in V$ is the start variable

What is a derivation?

It is a sequence of substitutions to obtain a string.

  • Ex: Let $G_1$ be the grammar that generates the string 000#111. Let the grammar $G_1$ have the following rule: A -> 0A1 A -> B B -> # The derivation of $G_1$ would be: A -> 0A1 -> 00A11 -> 000A111 -> 000B111 -> 000#111

What is a Context-Free Language?

Any language that can be generated by some context-free grammar.

For example, if u, v, and w are strings of variables and terminals, and A->w is a rule of the grammar, we say that uAv yields uwv. uAv -> uwv

Says that u derives v,

Designing Context-Free Grammars

Many CFLs are the union of simpler CFLs. So, if you need to construct a CFG for a CFL, you can break into simpler pieces. Ex: To get a grammar for the language {$0^n1^n|n>=0$} $\cup$ {$1^n0^n|n>=0$}:

  1. Construct grammar for the language {$0^n1^n|n>=0$}: $S_1$ -> $0S_11|\lambda$
  2. Construct grammar for the language {$1^n0^n|n>=0$}: $S_2$ -> $1S_20|\lambda$
  3. Add the rule $S$ -> $S_1|S_2$ to give the grammar: $S$ -> $S_1|S_2$ $S_1$ -> $0S_11|\lambda$ $S_2$ -> $1S_20|\lambda$

You can also construct a CFG for a language if it happens to be regular if you first construct a DFA for that language. (page 107)

Ambiguity

If a grammar generates a string in several different ways, then the string is ambiguous in that grammar.

To determine that the grammar generates the same string in several different ways, you need to determine if the string generates multiple parse trees.