What type of grammar is this?

258 Views Asked by At

I'm working on this problem:

Suppose a phrase-structure grammar has productions: $ S\to 1S0, S\to0A, A\to 0 $. What type of grammar is this, why?

Would this be considered a type 1 grammar? I'm having trouble differentiating between the grammar types, but I know this is a linear bounded automata, would that make it type 1?

1

There are 1 best solutions below

0
On

Your grammar is a linear grammar, a special case of context-free (or Type 2) grammar. A context-free grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol. A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.

In your case, the productions $S \to 1S0$ and $S \to 0A$ have exactly one nonterminal symbol on each side and the production $A \to 0$ has one nonterminal symbol on the left and no one nonterminal symbol on the right. It is not a regular (or Type 3) grammar, but, as context-free grammars are special cases of context sensitive (or Type 1) grammars, it is also a Type 1 grammar.