Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Grammar into normal form

  1. Mar 5, 2009 #1
    Hi everyone,

    I have a grammar to convert into a normal form, but I have no idea how to do that. And from this normal form, I have a lot of other things to do.

    Could you please convert me this grammar into a normal form:

    S --> aQ | a
    Q --> aQ | bbS | bS | b

    Thanks in advance,
  2. jcsd
  3. Mar 6, 2009 #2
    It appears that the language generated by this grammar consists of all strings of length at least 1, containing only terminal symbols a and b, such that the string starts with at least 1 a, and has no more than 2 b's in a row.

    Therefore, perhaps...

    S --> AQ | a

    A --> a
    B --> b
    D --> BB

    R --> AQ

    Q --> AQ | DR | DA | BR | BA | b

    Is that what you're after? I just kind of threw that together, so it can probably be cleaned up considerably (if it's right...)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook