context-free grammar

a context-free grammar is a 4-tuple $\text{[math]}$ , where

$\text{[math]}$ is a finite set called the variables,
$\text{[math]}$ is a finite set, disjoint from $\text{[math]}$ , called the terminals,
$\text{[math]}$ is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
$\text{[math]}$ is the start variable.

[cite:;from @sipser_comp_2012 definition 2.2]

if $\text{[math]}$ , and $\text{[math]}$ are strings of variables and terminals, and $\text{[math]}$ is a rule of the grammar, we say that $\text{[math]}$ yields $\text{[math]}$ , written $\text{[math]}$ . say that $\text{[math]}$ derives $\text{[math]}$ , written $\text{[math]}$ , if $\text{[math]}$ or if a sequence $\text{[math]}$ exists for $\text{[math]}$ and
$\text{[math]}$ the language of the grammar is $\text{[math]}$ .

the following is an example of a context-free grammar, which we call $\text{[math]}$ .
$\text{[math]}$ a grammar consists of a collection of substitution rules, also called productions. each rule appears as a line in the grammar, comprising a symbol and a string separated by an arrow. the symbol is called a variable. the string consists of variables and other symbols called terminals. the variable symbols often are represented by capital letters. the terminals are analogous to the input alphabet and often are represented by lowercase letters, numbers, or special symbols. one variable is designated as the start variable. it usually occurs on the left-hand side of the topmost rule. for example, grammar $\text{[math]}$ contains three rules. $\text{[math]}$ ’s variables are $\text{[math]}$ and $\text{[math]}$ , where $\text{[math]}$ is the start variable. its terminals are 0, 1, and #. you use a grammar to describe a language by generating each string of that language in the following manner.

write down the start variable. It is the variable on the left-hand side of the top rule, unless specified otherwise.
find a variable that is written down and a rule that starts with that variable. replace the written down variable with the right-hand side of that rule.
repeat step 2 until no variables remain.

for example, grammar $\text{[math]}$ generates the string 000111 the sequence of substitutions to obtain a string is called a derivation. a derivation of string 000111 in grammar $\text{[math]}$ is
$\text{[math]}$ you may also represent the same information pictorially with a parse tree. an example of a parse tree is shown in fig-cfg-parse-tree-1.
$\text{[math]}$ all strings generated in this way constitute the language of the grammar. we write $\text{[math]}$ for the language of grammar $\text{[math]}$ . some experimentation with the grammar $\text{[math]}$ shows us that $\text{[math]}$ is $\text{[math]}$ . any language that can be generated by some context-free grammar is called a context-free language (CFL). for convenience when presenting a context-free grammar, we abbreviate several rules with the same left-hand variable, such as $\text{[math]}$ and $\text{[math]}$ , into a single line $\text{[math]}$ , using the symbol $\text{[math]}$ as an "or".
the following is a second example of a context-free grammar, called $\text{[math]}$ , which describes a fragment of the English language.
$\text{[math]}$ grammar $\text{[math]}$ has 10 variables (the capitalized grammatical terms written inside brackets); 27 terminals (the standard English alphabet plus a space character); and 18 rules. strings in $\text{[math]}$ include:

a boy sees
the boy sees a flower
a girl with a flower likes the boy

each of these strings has a derivation in grammar $\text{[math]}$ . the following is a derivation of the first string on this list.
$\text{[math]}$

consider grammar $\text{[math]}$ . the set of rules, $\text{[math]}$ , is
$\text{[math]}$ this grammar generates strings such as $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ . you can see more easily what this language is if you think of a as a left parenthesis "(" and $\text{[math]}$ as a right parenthesis ")". viewed in this way, $\text{[math]}$ is the language of all strings of properly nested parentheses. observe that the right-hand side of a rule may be the empty string $\text{[math]}$ .
[cite:@sipser_comp_2012 example 2.3]

[cite:@sipser_comp_2012 chapter 2 context-free languages]

build cfg's for each of the following languages:

$\text{[math]}$ . $\text{[math]}$
$\text{[math]}$ . $\text{[math]}$
$\text{[math]}$ . $\text{[math]}$ or $\text{[math]}$
the empty language. $\text{[math]}$
all the words over $\text{[math]}$ in which the string $\text{[math]}$ appears. $\text{[math]}$
$\text{[math]}$ $\text{[math]}$

how about
$\text{[math]}$

[cite:@sipser_comp_2012 chapter 2 context-free languages, designing context-free grammars]
[cite:@sipser_comp_2012 chapter 2 context-free ambiguity]