Introduction to Grammars

Advertisements

Previous Page
Next Page  

n the literary sense of the term, grammars denote syntactical rules for conversation in natural languages. Linguistics have attempted to define grammars since the inception of natural languages like English, Sanskrit, Mandarin, etc.

The theory of formal languages finds its applicability extensively in the fields of Computer Science. Noam Chomsky gave a mathematical model of grammar in 1956 which is effective for writing computer languages.

Grammar

A grammar G can be formally written as a 4-tuple (N, T, S, P) where −

  • N or VN is a set of variables or non-terminal symbols.

  • T or ∑ is a set of Terminal symbols.

  • S is a special variable called the Start symbol, S ∈ N

  • P is Production rules for Terminals and Non-terminals. A production rule has the form α → β, where α and β are strings on VN ∪ ∑ and least one symbol of α belongs to VN.

Example

Grammar G1 −

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

Here,

  • S, A, and B are Non-terminal symbols;

  • a and b are Terminal symbols

  • S is the Start symbol, S ∈ N

  • Productions, P : S → AB, A → a, B → b

Example

Grammar G2 −

(({S, A}, {a, b}, S,{S → aAb, aA → aaAb, A → ε } )

Here,

  • S and A are Non-terminal symbols.

  • a and b are Terminal symbols.

  • ε is an empty string.

  • S is the Start symbol, S ∈ N

  • Production P : S → aAb, aA → aaAb, A → ε

Derivations from a Grammar

Strings may be derived from other strings using the productions in a grammar. If a grammar G has a production α → β, we can say that x α y derives x β y in G. This derivation is written as −

x α y ⇒G x β y

Example

Let us consider the grammar −

G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } )

Some of the strings that can be derived are −

S ⇒ aAb using production S → aAb

⇒ aaAbb using production aA → aAb

⇒ aaaAbbb using production aA → aAb

⇒ aaabbb using production A → ε

Advertisements