Results 1 to 6 of 6

Math Help - Forming a language with Regular Grammar

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    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.
    Last edited by pikminman; January 19th 2010 at 11:18 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    I assume you wrote a description of a nondeterministic finite automaton that accepts this language. I think it is correct.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Quote Originally Posted by emakarov View Post
    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"
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 27th 2011, 03:42 PM
  2. Simplification grammar
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: June 30th 2010, 06:16 AM
  3. Grammar problem
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 29th 2010, 06:42 AM
  4. context-free language and grammar
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 28th 2010, 05:42 PM
  5. Regular Grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 20th 2010, 09:58 AM

Search Tags


/mathhelpforum @mathhelpforum