Phrase Structure Grammars

Terminology:

• vocabulary V is a finite, nonempty set of elements called symbols
• alphabet is a synonym for vocabulary
• word over V is a string of finite length of elements of V.
• sentence is a synonym for word
• empty string denoted by lambda l is the string containing no symbols.
• null string is a synonym for empty string
• V* is the set of all words over V
• language over V is a subset of V*

Grammar has

• vocabulary V - set of symbols used to derive members of the language.
• terminals - elements of the vocabulary which cannot be replaced by other symbols
• nonterminals – elements of the vocabulary which can be replaced by other symbols
• start symbol – denoted by S which is the element of the vocabulary that we always begin with.
• productions – rules that specify when we can replace a string from V* with another string
• z₀ →z₁ – production saying that z₀ can be replaced by z₁

Types of Phrase-Structure Grammars

• type 0 – phrase-structure – no restrictions on productions
• type 1 – context-senstitive – productions are of the form w₁ → w₂ where the length of w₂ is greater than the length of w₁ or of the form w₁ →l
• type 2 – context-free grammars – productions only of the form w₁ → w₂ where w₁ is a single symbol that is not a terminal symbol.
• type 3 – regular grammars productions only of the form w₁ → w₂ with w₁ = A and either w₂ = aB or w₂ = a, where A and B are nonterminal symbols and a is a terminal symbol, or with w₁ = S and w₂→l