1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proove this Grammer generates multiples of 3

  1. Sep 4, 2013 #1
    1. Problem Statement
    C ::= C 0 | A 1 | 0
    A ::= B 0 | C 1 | 1
    B ::= A 0 | B 1

    Prove that the numbers generated are all multiples of 3.

    3. The attempt at a solution

    I have the solution, but am having trouble understanding it.
    http://cm.bell-labs.com/who/ravi/teddy/solutions/XX0221.html [Broken]

    Firstly, a question of semantics. They say that nonterminal "C" produces numbers of the form 3n. Doesnt this need to be proven somehow? Also, how do they reconcile the fact that in order to produce numbers of the form 3n, you must use the other nonterminals, doesn't this mean that we are no longer talking about nontermincal C, but about the grammer itself? This sounds like circular reasoning to me.

    Also, their description of nontermincal C completely omits discussion of nonterminal B, isn't this problematic?

    Finally, they do not integrate the 3 nonterminals of the grammer in any way, so I'm having trouble understanding how I can formally integrate the three cases potentially generating multiples of three into saying definetively that the grammer generates multiples of 3.

    Please help me understand this a bit better, the theoretical side of Computer Science is confusing me quite a bit here.

    Thank you!
    Last edited by a moderator: May 6, 2017
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted

Similar Discussions: Proove this Grammer generates multiples of 3
  1. Synchronous generator (Replies: 2)

  2. Entropy Generation (Replies: 6)