Previous
Next
Grammer
In 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.

Contributor's Info

Created:
0Comment
+1
0
-1
Grammer | Theory of Computation
  1. Grammar has set of rules to generate the strings of a language.
  2. 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 : ({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

Contributor's Info

Created:
A
 Edited:
0Comment
+1
0
-1