We have described two types of grammars:

• regular grammars - generate the regular languages
• context-free grammars - generate the context-free languages

• these are specific examples of a general type of grammar
• known as the  phrase structure grammars (PSG's)
• all are described using productions
• the "phrases" are the RHS and LHS of productions, just as in natural language:

• <noun phrase> ® <article> <noun>
• <noun phrase> ® <preposition> <noun>
• etc.

1. A finite alphabet of letters called terminal symbols
2. A finite set of symbols called non-terminal symbols
3. A special non-terminal S called the sentence symbol
4. A finite set of productions of the form:

• the lhs-string (lefthand-side-string) and rhs-string (righthand-side-string) are strings of terminal and non-terminal symbols
• the lhs-string must have at least one non-terminal
• the rhs-string may be empty

We have already introduced the r.e. languages.

Q: Is there a PSG version of the r.e. languages?
A: Yes!

The Type 0 languages are exactly the (general) phrase structure grammars.

Example:

• 3 applications of production 1 will create the sentential form: aaaSBABABA (3 a's and 3 SB's)
• applying production 2 we get: aaaabABABABA
• notice: #a's = #A's = #b's and B's =4
• here's where things get interesting:
• production 3 lets you change the order of items in the sentential form!!
• quite unlike context-free grammars
• one application of prod 3 gets us: aaaabBAABABA
• another: aaaabBABAABA
• another: aaaabBBAAABA
• repeated applications will get us: aaaabBBBAAAA
• finally, using prod 4,5,6 we get aaaabbbbaaaa = a⁴b⁴a⁴
• in fact, this grammar generates exactly aⁿbⁿaⁿ
• a non-context-free language!

Part 1: Any type 0 language L with grammar G can be recognized by a Turing machine.

• proof is by construction
• resembles the construction method used to create a PDA that recognizes the language generated by a CFG
• we show how to construct a non-deterministic TM that will recognize strings from L

• create derivations starting with S, and
• check at each step to see if the required sentence has been derived

1. the tape will be initialized (by the initialization part of the program) with the input string (delimited by $-signs), followed by a string called the current sentential form, initialized to S
2. the TM will have a subroutine called rewrite (corresponding to the pop state for the CFG-PDA) which will do the following:
(a) look for the LHS of a production in the sentential form, e.g. the AB in AB ® BA
(b) replace the LHS by the RHS (non-deterministically)
3. compare the sentential form with the input; if the same, accept, otherwise, continue.

Part 2: Any TM has a corresponding Type 0 grammar

Proof: See pp. 576-585 (!!!)

Between the context-free languages and the r.e. languages sits an important class of languages, called the context sensitive languages.

A PSG whose productions have the property that

is called a context-sensitive grammar (CSG).

The language generated by a CSG is called a context-sensitive language (CSL).

Notes:

• context-sensitive refers to the fact that some CSL productions, e.g. BAC ® BXYC
• impose the condition that A can be replaced by XY only if it is in the context B..C
• the rewrite rules consider context
• like natural languages, and
• unlike computer languages
• the CSL's have their own machines, which can be thought of as TM's with a bounded-length tape, called

• there are recursive languages not recognized by LBA
• there are CSL's not recognized by PDA
• the CFL's are proper subset of the CSL's
• the CSL's are a proper subset of the recursive languages

This uses the same "diagonal" argument used to construct L₁, a language that is r.e. but not recursive.

1. Enumerate all CSG's: CSG₁, CSG₂, …
2. Enumerate all input strings x₁, x₂, …

1. L₃ is recursive. Left to the reader.
2. L₃ is not context-free. See the corresponding theorem for L₁.

• the final cast of language classes:
• some generated by PSG's (Chomsky hierarchy)
• these are types 0,1,2,3 seen below
• others are not described by grammar type
• each class is a proper subset of the next