The grammar of computer terminology is much like that of a natural language; a set of rules for putting things together. Each grammar corresponds to a language. In this chapter, we focus on a special type of grammar called context-free grammar. Then we discuss push-down automata, which is a model of a computer that is more powerful than finite automata.
What is GRAMMAR in TOC?
In formal terminology, grammar is a set of production rules. They are also called language generators, which consist of terminal symbols, non-terminal symbols, starting symbols and rules. The rules describe how to form strings from the language alphabets that are valid according to the syntax of the language. Grammar does not define the meaning of the queues. The reality of a sentence is specified by the grammar of a language. Each language, generated by some grammar can be recognized by some automation.
Definition: Grammer
A grammar is a Quadruple, G = (V, T, P, S)
Where,
V is the finite set of variables or non-terminals
T is a finite set of terminals
P is a set of production rules.
A → α, where
- A is a string of symbols from (VUT)+
- α is a string of symbols from (VT)*
- S is the start symbol and S ε V.
Note: Variables can be replaced by other variables or terminals and it is represented by capital letters.
Read More | Theory of Computation
Types of Grammar
Noam Chomsky who is the founder of formal language theory has classified the grammar into various categories according to the minimal automation required to recognize them.
They are:
- Type 0 grammar (Phrase structured/Unrestricted grammar)
- Type 1 grammar (Context Sensitive grammar)
- Type 2 grammar (Context Free grammar)
- Type 3 grammar (Regular grammar)
What is passing? Explain.
The sequence of substitutions used to obtain a string is called derivation or parsing. It means replacing an instance of a given string non-terminal. The right-hand side of the production whose left-hand side contains the non-terminal to be replaced.
For example, consider the following productions.
S →x α y
α → β
then the replacement of α by β in x α y is called parsing or derivation?
S →x α y
→x α y
Parsing produces a new string from a given stream. Therefore, derivation can be used repeatedly to obtain a new string from a given string. If the string obtained after parsing contains only terminal symbols, then no further derivations are possible.