Grammars

Grammars
A grammar is a set of rules which are used to construct a language (combine words to generate sentences).

Sentence = noun verb noun
Verb = went, eat, reading
Noun = lesson, boy, school, book

Boy reading book

may be there are sentences have no meaning = book reading boy
G=(N, T, S, P)
N= set of nonterminal symbols (parts of speech (sentence, noun, verb, …))
T= set of terminal symbols (words, or symbols in)
S= start symbol non-terminal used to start every derivation.
P= set of productions.

Example
productions: S a S
S ?




The derivation for aaaa is:
S => aS
=> aaS
=> aaaS
=> aaaaS
=> aaaa? = aaaa
RE= a+

Example
productions: S SS
S a
S ?
S SS / a / ?
Derivation of aa
S => SS
=> SSS
=> SSa
=> SSSa
=> SaSa
=> ?aSa
=> ?a?a = aa








TYPES OF GRAMMAR
Type 0:
unrestricted grammars include all formal grammars. They generate exactly all languages that can be recognized by a Turing machine. The language that is recognized by a Turing machine is defined as all the strings on which it halts.


Type 1:
context-sensitive grammars generate the context-sensitive languages. These grammars have rules of the form KAL I KJL with A a nonterminal and K, L and J strings of terminals and nonterminals. The strings K and L may be empty, but J must be nonempty. The rule S I M is allowed if S does not appear on the right side of any rule. The languages described by these grammars are exactly all languages that can be recognized by a non-deterministic Turing machine whose tape is bounded by a constant times the length of the input.

Type 2:
context-free grammars generate the context-free languages. These are defined by rules of the form A I J with A a nonterminal and J a string of terminals and nonterminals. These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton. Context free languages are the theoretical basis for the syntax of most programming languages.