Automata Grammar
Grammar is a finite set of formal rules for generating syntactically correct sentences or meaningful correct sentences.
A Grammar can contain mainly two elements: Terminal and Non Terminal.
Terminal Symbols
It is a portion of the sentence generated by using grammar. It is denoted by using small letters, such as a, b, c, d, etc.
Non Terminal Symbols
It takes part in the formation of a sentence, but not part of it. It is denoted by using capital letters, such as A, B, C, D, etc. It is also called auxiliary symbols.
Formal Definition of Grammar
A grammar G is a 4-tuple
G = (N,Σ,P,S)
- N- It is a finite, non-empty set of symbols called variables, or non-terminals, or syntactic categories,
- Σ- It is an alphabet of symbols called terminals, where N ∩ Σ = φ,
- P- It is a finite set of "productions" or "rules",
- S- It is the start or initial non terminal symbol of the grammar.
Notations of Grammar
These are some notations that help you understand the concept of grammar-
- Non-terminal symbols are represented as A, B, C, …. ∈ V
- Terminal symbols are represented as a, b, c, … ∈ T
- Generic symbols are represented as X, Y, Z, ...∈ V ∪ T
- Strings over T are represented as p, q, r, s, … ∈ T∗
- Strings over V ∪ T represents α, β, γ, δ, … ∈ (V ∪ T)∗
Language of a Grammar
Let's say G is a grammar with start variable S and terminals Σ, then the language generated by L is-
L(G) = {w | w ∈ ∑* and S ⇒+w}
Types of Grammar
The Noam Chomsky classifies the types of grammar into four types: Type0, Type1, Type2 and Type3. It is also called the Chomsky hierarchy of grammar. These are types of grammar used in the theory of computation.
Types | Grammars | Automata | Languages | Productions |
Type-0 | Unrestricted Grammar | Turning Machine | recursively enumerable | α → β |
Type-1 | Context Sensitive Grammar | Linear-bounded Machine | context-sensitive | α → β, |β|>=|α| |
Type-2 | Context Free Grammar | Pushdown Automata | context-free | A → α |
Type-3 | Regular Grammar | Finite-State Automata | regular | A → αB, A -> a |
where, A and B are non-terminal symbols, α and β are string of terminals and non-terminals and a is terminal symbol.
Arden's Theorem
Unrestricted Grammar