0
$\begingroup$

I'm not sure how to create the phase-structure grammer of the set

$\{10^n \mid n \ge 0\}$

So if $G = (V, T, S, P)$ where $V$ is the vocabulary set, $T$ is a subset of $V$, $S$ is the start position, and $P$ are the productions. What can I use for $V,T,S,P$?

1 Answers 1

2

The set consists of all strings of the form $10^*$, i.e., a $1$ followed by zero or more $0$'s. Thus, you want to generate a $1$, change non-terminals and generate $0$'s.

$\begin{align*} S&\to 1\\ S&\to 1Z\\ Z&\to 0\\ Z&\to 0Z \end{align*}$

The first production generates the word $1$, which is $10^0$. The second production generates a $1$ and then switches over to the non-terminal $Z$, which generates $0$'s. The third production generates the last $0$ of a string, while the fourth generates a $0$ and allows you to continue generating more $0$'s.

From this you should be able to sort out $V$ and $T$; altogether you're using four symbols, two of which are terminal, and two of which are non-terminal.