Phrase-Structure GrammarsPhrase-Structure Grammars

Definition:

A phrase-structure grammar is defined as an ordered quadruple of the form

where:

• is the set of nonterminals, called "variables ."

• is the set of terminals.

• is the set of production rules, defined below .

• is the starting variable.

We assume that , but .

Productions have the form where ,

1. , written

2. 

   and such that

3. There is at least one member of of the form

4. Let, , then must contain at least one member of .

5. At least one member must have

As usual, The Language Generated by , , is the set of strings such that there is a derivation

___________________________________________________________________________

A Natural Example of a Non-Context Free Grammar.

or

An Example of a Non-Context Free Grammar

		the
		manbook
		men books
		reads
		read

Productions:

the man reads the book

the men read the book

the man reads the books

the men read the books

__________________________________________________________

The Chomsky Hierarchy: