CSC 341: February 9, 2007

From CSWiki

Instructor's notes for the class session

Some languages, even ones that are fairly easy to describe, aren't regular. In other words, some problems, even ones that are fairly easy to state formally, can be solved by finite automata. But, of course, the model of computation that is realized in finite automata is extremely simple one. Perhaps we can make more progress by switching to a different model of computation -- either an automaton design that is enriched by the addition of some better mechanism for storage, or a model based on a completely different idea.

In section 2.1, we take the second approach. Think of a computational step as the application of some syntactic operation to a string of symbols, yielding a revised string of symbols. The instruction set of a computer designed on this model will be a set of licensed syntactic operations.

Context-free grammars are a class of computers designed in this way. To specify a context-free grammar, we specify a finite set of symbols called terminals that serves as the alphabet for the grammar's possible outputs, and a finite, non-empty set of symbols called variables that can appear in strings at intermediate steps in the grammar's processing. One of the variables is distinguished as the start variable; when the computation begins, the initial string on which the syntactic operations can be performed is the one-symbol string in which the only symbol is the start variable.

The syntactic operations are specified by rules. In a context-free grammar, there can be only finitely many of these, and each one has a very specific form: It licenses the replacement, at any point of the current string, of one variable (the rule's left-hand side) with any finite string of symbols (its right-hand side), which may include both variables and terminals. The following computational step operates on the result of this replacement rather than on the original string.

Context-free grammars are nondeterministic, since at any step one can apply any rule (provided that its left-hand side occurs in the current string), and one can apply it to any occurrence of its left-hand side in the current string. The computation ends when the current string consists entirely of terminals, and in that case the grammar is said to have generated or output that string. In some cases, it is possible for a computation to become wedged, in that the current string contains one or more variables, but no variable that is the left-hand side of any rule; in that case, the computation aborts without generating anything.

The language of a context-free grammar is the set of strings of terminals that it generates.

Every regular language is the language of some context-free grammar, but the converse is not true.

[edit]

Study questions

Is the string the flower sees a flower with a girl with a flower a member of $L (G 2)$ ? If so, construct a parse tree for it; if not, prove that $G 2$ does not derive it.
Construct a context-free grammar that generates only the empty string.
Construct a context-free grammar that does not generate any string.
Construct a context-free grammar $G$ such that $L (G)$ is the set of all palindromes on the alphabet $\{\texttt{a}, \texttt{b}\}$ .

[edit]

Proposed Solutions

This string is indeed a member of $L (G 2)$ . Instead of giving a parse tree for it, I will give a derivation.

    <SENTENCE> <NOUN-PHRASE> <VERB-PHRASE>
               <CMPLX-NOUN> <VERB-PHRASE>
               <ARTICLE> <NOUN> <VERB-PHRASE>
               the <NOUN> <VERB-PHRASE>
               the flower <VERB-PHRASE>
               the flower <CMPLX-VERB> <PREP-PHRASE>
               the flower <VERB> <NOUN-PHRASE> <PREP-PHRASE>
               the flower sees <NOUN-PHRASE> <PREP-PHRASE>
               the flower sees <CMPLX-NOUN> <PREP-PHRASE> <PREP-PHRASE>
               the flower sees <ARTICLE> <NOUN> <PREP-PHRASE> <PREP-PHRASE>
               the flower sees a <NOUN> <PREP-PHRASE> <PREP-PHRASE>
               the flower sees a flower <PREP-PHRASE> <PREP-PHRASE>
               the flower sees a flower <PREP> <CMPLX-NOUN> <PREP-PHRASE>
               the flower sees a flower with <CMPLX-NOUN> <PREP-PHRASE>
               the flower sees a flower with <ARTICLE> <NOUN> <PREP-PHRASE>
               the flower sees a flower with a <NOUN> <PREP-PHRASE>
               the flower sees a flower with a girl <PREP-PHRASE>
               the flower sees a flower with a girl <PREP> <CMPLX-NOUN>
               the flower sees a flower with a girl with <CMPLX-NOUN>
               the flower sees a flower with a girl with <ARTICLE> <NOUN>
               the flower sees a flower with a girl with a <NOUN>
               the flower sees a flower with a girl with a flower

$S \rightarrow \varepsilon$
$S \rightarrow S$ . This grammar will run forever, and will thus not return any strings. An alternative grammar with the same result is that which provides no transitions at all, formally described as four-tuple $( \{S\}, \empty, \empty, S )$ . See Definition 2.2 for reference.
$S \rightarrow A$