Grammars, Languages Types Homework Help, Assignment Help, Online Tutor, Tutoring

Submit Assignment

* *

Payment Online Assignment Help

Trigonometry Homework

Homework Help

sfsf

Grammars Languages Types

Using grammars to specify languages also leads us to a natural way of classifying languages. However, we do want to state some of the results, without proof, so that the reader may appreciate more the subject matter.

In the following, we shall use A and B to denote arbitrary nonterminals, a and be to denote arbitrary terminals, and and to denote arbitrary strings of terminals and nonterminals. A grammar is said to be a type-3 grammar if all productions in the grammar are of the forms:

A a                                 (1)

A aB                               (2)

Or, equivalently, of the forms,

A a

A Ba                               (3)

In other words, in any production the left-hand string is always a single non-terminal and the right-hand string is either a terminal followed by a non-terminal.

In a type-2 grammar, every production is of form

A

In other words, in any production the left-hand string is always a single non-terminal. Clearly, a type-3 grammar is trivially also a type-2 grammar.

In a type-1 grammar, for every production,

The lengths of is larger than or equal to the length of . For example, the production,

A ab

A aA

aAb aBCb

all satisfy the condition, while the productions,

aA a

ABc bc

Do not. Again, clearly a type-3 or a type-2 grammar is also trivially a type-1 grammar.

A phase structure as defined above with no restriction is referred to as a type-0 grammar.

Corresponding to different types of grammar, there are different types of languages. Thus, a language is said to be a type-i (i = 0, 1, 2, 3) language if it can be specified by a type-i grammar, but it cannot be specified by a type (i + 1) grammar. For example, the language,

L = {ak bk|k ≧1}

Is a type-2 language because it can be specified by the type-2 grammar

A aAb

A ab

Yet, on the other hand, L cannot be specified by a type-3 grammar. Thus, corresponding to the four types of grammars, we also have four types of languages. There are some questions that arise naturally.

Are there languages that are not type-0 languages? The answer is affirmative. In other words, there are languages that cannot be specified by phrase structure grammars.

How about all the programming languages? They can be specified by phrase structure grammars. As a matter of fact, all of them are (almost) type-2 languages.

Is each class of type-i languages nonempty? The answer is affirmative but is not as obvious as it seems. (Since we choose the definitions of the various types of grammars in a seemingly arbitrary manner, the possibility that any language that can be specified by a type-i grammar can also be specified by a type-(i + 1) grammar is not precluded.)

From a more practical point of view, there is the important question of determining whether a given string indeed belongs to a language specified by a grammar, and if so, how that string is derived. However, in practice, for example when we want to construct a complier for a programming language we need to determine if a given string is indeed a legitimate sentence in the language. Then we need to discover how the sentence was derived so that we can translate it (into machine instruction codes) according. Conceptually, these can all be done by exhaustive search, but efficient algorithms have been developed to perform the tasks.