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

Challeng in simplifying the Grammer

  1. Jan 10, 2009 #1
    challeng !!!!! in simplifying the Grammer

    It is a challeng grammer to be simplified by removing all useless, unit, and epsilon (empty string)-productions:

    S -> abAB |CD
    A -> aBA |epsilon (empty string)
    B -> ABb |A |epsilon (empty string)
    C -> bb |CD
    D -> bD

    if no one answer it :smile:
  2. jcsd
  3. Jan 25, 2009 #2
    Re: challeng !!!!! in simplifying the Grammer

    D is a useless symbol

    The grammar produces all strings beginning with ab and followed any sequence of a and b symbols. An equivalent grammar follows:

    S -> ab H
    H -> Ha | Hb | epsilon
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook