Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.