# Thread: Forming a language with Regular Grammar

1. ## Forming a language with Regular Grammar

Can somebody help me with this question.

Construct a regular grammar that generates the language L over the alphabet {0,1}, where

L = {1,1000,1000000,1000000000,...}

so that a string of binary digits belongs to L if and only if it consists of the digit 1 followed by a string of 3n Zeroes, for some non - negative integer n. Specify your formal grammar in Backus-Naur form.
I thought this might be the solution but am not sure:

S -> 1<T1> | 1<F>
T1 -> 0<T2>
T2 -> 0<T3>
T3 -> 0<T1>| 0<F>
F -> <EMPTY SET>

Any help would be greatly appreciated.

2. I assume you wrote a description of a nondeterministic finite automaton that accepts this language. I think it is correct.

3. Originally Posted by emakarov
I assume you wrote a description of a nondeterministic finite automaton that accepts this language. I think it is correct.

I'm not quite sure if I did. I now know that this is correct, I just dont know how to generate all the elements of my language.

4. What exactly are you unsure of: (1) that the description you wrote described a nondeterministic finite automaton, (2) what are the words of the language, or (3) how to use the automaton to accept the words of the language?

5. Originally Posted by emakarov
What exactly are you unsure of: (1) that the description you wrote described a nondeterministic finite automaton, (2) what are the words of the language, or (3) how to use the automaton to accept the words of the language?

Hmm, well I suppose that I'm just wondering if

S -> 1<T1> | 1<F>
T1 -> 0<T2>
T2 -> 0<T3>
T3 -> 0<T1>| 0<F>
F -> <EMPTY SET>

constitutes a "regular grammar"

6. I am sorry, I missed that the problem statement says to construct a regular grammar; that's why I thought about automata. Yes, what you have is a regular grammar that generates the required language.

In addition, this can also be considered a description of a nondeterministic finite automaton. From this it is pretty obvious that regular grammars and NDFAs describe the same class of languages (it's a standard theorem).