Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

seanwalsh1984

  • 3 years ago

Let the alphabet = {a, b}. Part (a): Give a Context Free Grammar for the language {a^nb^m | n > 2m}. I have NO clue at all.

  • This Question is Closed
  1. Tomas.A
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

    if zero b's then there must be at least one a if one b then there must be at least three a's if two b's then tehre must be at least five a's and so on

  2. Tomas.A
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

    also first should come a's and only then b's

  3. Tomas.A
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

    so we start with S -> aQT (we must have at least one a) Q -> aQ | ε (we can generate any number of a's before b) T -> aaTb | ε (if we create at least one b we must put two a's before b)

  4. seanwalsh1984
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Wow! Thanks! Here is what I came up with this morning toying around. \[S_0 \rightarrow aaS_1b | aaS_1b | aS_1\] \[S_1 \rightarrow S_0\epsilon | a\] Is this equivalent?

  5. Tomas.A
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 4

    no, for example you can't get just a, but according to rules you should be able to however maybe you made mistake by typing because if it will be S_1 -> S_0|ϵ|a i think it would be ok and aaS_1b is same as aaS_1b so why you mention it 2 times? :D

  6. seanwalsh1984
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes you are right, I mistyped, and my computer was acting up. I did have S1->S0 | epsilon | a. Thanks for the help!

  7. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy