انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

Grammar

each Type of  grammar G is defined as a mathematical system consisting of a quadruple <N,? , P, S>, where

N

is an alphabet, whose elements are called nonterminal symbols.

?

is an alphabet disjoint from N, whose elements are called terminal symbols.

P

is a relation of finite cardinality on (NE? )*, whose elements are called production rules.

Moreover, each production rule (a,b ) in P, denoted a® b , must have at least one nonterminal symbol in a . In each such production rule, a is said to be the left-hand side of the production rule, and b is said to be the right-hand side of the production rule.S is a symbol in N called the start

Example  <N, ? , P, S> is a grammar if N = {S},? = {a, b}, and P = {S® aSb, S®l }. By definition, the grammar has a single nonterminal symbol S, two terminal symbols a and b, and two production rules S ®aSb and S®l . Both production rules have a left-hand side that consists only of the nonterminal symbol S. The right-hand side of the first production rule is aSb, and the right-hand side of the second production rule is l .

If N2 = {S}, ?2 = {a, b}, and P2 = {S ®aSb, S ®l, ab ®S} then <N2, ?2, P2, S> is not a grammar, because ab ®S does not satisfy the requirement that each production rule must contain at least one nonterminal symbol on the left-hand side.

Type of Grammars: or hierarchy of Grammar

The four classes are Type 0 summarized in the table below:

Example

SabN®Sab\ aaN

N®bb                                    Type 0

Sab®aaSb\aa                         Type 1

S®aSb\ab                              Type 2

S®aS\a\Sa                                     Type 3

DONE

Instructor: Mohamed U. Mahdi