Given the following grammars with start symbol $\langle S \rangle$, specify the type ($0$, $1$, $2$ or $3$)

31 Views Asked by At

So I'm working on this problem set and I'm having some trouble figuring out what type each one of these are. I think (a) is type $0$ and really can't tell for (b). I know the difference between each type but for some reason can't seem to figure out these two. I think how they are set up might be messing me up . Also review for my first quarter exam.

(a) $\begin{align}\langle S \rangle &= aaa \langle T \rangle bb\\ \langle T \rangle &= a \langle T \rangle \langle T \rangle b | \lambda \end{align}$

(b) $\begin{align} &\langle S \rangle = a \langle Q \rangle bc | \lambda \\ &\langle Q \rangle = a \langle Q \rangle b \langle T\rangle | \lambda\\ &b \langle T \rangle bc = \langle S\rangle | bbcc\\ & \langle T \rangle b = b \langle T\rangle \end{align}$

1

There are 1 best solutions below

0
On

What does $\lambda$ mean? Does it mean the empty string? If yes, this is more commonly expressed as $\epsilon$. Here, I just assume it this is what you mean.

a) actually is context-free, or type 2, because all production rules only have a single non-terminal symbol on their left side and no rule requires any context.

b) is type 0, because production rule no 3. is shortening on the first alternative, which isn't allowed for type 1 grammars and because it has the starting symbol $<S>$ on the right side, which isn't allowed for type 1 grammars neither.