Results 1 to 8 of 8

Thread: Right Linear Grammars

  1. #1
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Question Right Linear Grammars

    I have this one problem that I'm stuck on in terms of right linear grammars. I've listed the directions and my current answer below. If you guys could look it over that'd be great:

    Write a right-linear grammar for each of the following languages.


    1. 0∗ 1∗


    A language that has zero more instances of 0 followed by zero more instances of 1.

    S 0A
    A 0A
    A 1A
    A 1
    A 0
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,706
    Thanks
    1033

    Re: Right Linear Grammars

    Maybe this:

    $S \to AB$
    $A \to 0A$
    $A \to \varepsilon$
    $B \to 1B$
    $B \to \varepsilon$

    Not sure what a right-linear grammar is. I am kinda guessing a little here. It appears to me that you can get expressions like the following:

    01100010101010100

    Essentially, you are allowing any string that begins with a zero followed by at least one more digit. All digits after the first zero are either zero or one.
    Last edited by SlipEternal; Jun 30th 2017 at 09:38 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Re: Right Linear Grammars

    Here's the formal definition of a Right Linear Grammar:

    Formal definition of Right Linear Grammars

    A right linear grammar is a 4-tuple <T, N, S, R>, where:

    1. N is a finite set of non-terminals


    2. T is a finite set of terminals, including the empty string

    3. S is the start symbol

    4. R is a finite set of rewriting rules of the form A-> xB or A-> x, where A and B
    stand for non-terminals and x stands for a terminal.

    Formal example:
    G1 = <T, N, S, R>, where T = {a, b}, N = {S, A, B}, and

    Answer:

    S -> aA

    A -> aA

    A -> bB

    B -> bB

    B -> b
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,706
    Thanks
    1033

    Re: Right Linear Grammars

    Then the answer i provided should work
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Re: Right Linear Grammars

    Also does this Grammar look right?

    (D) (aa∗ bb∗)/c

    S→ XY
    X→ aaB
    B→ bbX
    Y → c
    X → ε
    B → ε
    Last edited by marsandfruit; Jun 30th 2017 at 11:01 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,706
    Thanks
    1033

    Re: Right Linear Grammars

    Currently, you can only get strings like this:

    c
    aac
    aabbc
    aabbaac
    aabbaabbc

    I'd suggest the following:

    $S \to XY$
    $X \to aaX$
    $X \to bbX$
    $X \to \varepsilon$
    $Y \to c$

    Now, you can get any of the following:
    c
    aac
    bbc
    aaaac
    aabbc
    bbaac
    bbbbc
    etc.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Re: Right Linear Grammars

    I just re-did the problem and read it as: A language that can end in c or c and a and b with instances of zero or more a’s and zero or more b’s.

    I ended up coming up with this grammar:

    S → ABC

    A → aA

    A→ ε

    B→ bB

    B→ ε

    C → c


    The reason why I re-did it was because the position of the Kleene star
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,706
    Thanks
    1033

    Re: Right Linear Grammars

    I am by no means an expert on grammars. I am not even sure I understand the notation. What do the parentheses mean? What does the forward slash mean?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear Algebra Linear maps dealing with linear independence.
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: Mar 22nd 2013, 02:02 PM
  2. Replies: 3
    Last Post: Mar 8th 2013, 05:04 AM
  3. Replies: 7
    Last Post: Oct 10th 2011, 03:06 PM
  4. Context Free Grammars - nobody was able to answer
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: May 7th 2010, 10:15 AM
  5. Constructing grammars
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 19th 2009, 05:45 AM

Search Tags


/mathhelpforum @mathhelpforum