Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.
Quota: 0 / 30Donate
According to Chomsky’s hierarchy, grammar is divided into 4 types as follows:
Type 0: Unrestricted Grammar:
Type-0 grammars include all formal grammar. Type 0 grammar languages are recognized by the touring machine. These languages are also known as the Recursively Enumerable languages.
Grammar Production in the form of α ⟶ β where
α is ( V + T)* V ( V + T)* V : Variables T : Terminals.
β is ( V + T )*
In type 0 there must be at least one variable on the Left side of production.
Sab --> ba A --> S
Here, Variables are S, A, and Terminals a, b.
Type 1: Context-Sensitive Grammar
Type-1 grammars generate context-sensitive languages. The language generated by the grammar is recognized by the Linear Bound Automata
In Type 1
α ⟶ β α <= β
That is the count of symbols in α is less than or equal to β
Also β ∈ (V + T)+
i.e. β can not be ε
S --> AB AB --> abc B --> b
Type 2: Context-Free Grammar: Type-2 grammars generate context-free languages. The language generated by the grammar is recognized by Pushdown automata. In Type 2:
| α | = 1.
S --> AB A --> a B --> b
Type 3: Regular Grammar: Type-3 grammars generate regular languages. These languages are exactly all languages that can be accepted by a finite-state automaton. Type 3 is the most restricted form of grammar.
Type 3 should be in the given form only :
V --> VT / T (left-regular grammar) (or) V --> TV /T (right-regular grammar)
S --> a
The above form is called strictly regular grammar.
There is another form of regular grammar called extended regular grammar. In this form:
V --> VT* / T*. (extended left-regular grammar) (or) V --> T*V /T* (extended right-regular grammar)
For example :
S --> ab
Click here to submit your answer.