Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

seanwalsh1984

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.

  • one year ago
  • one year ago

  • This Question is Closed
  1. Tomas.A
    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

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

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

    • one year ago
  3. Tomas.A
    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)

    • one year ago
  4. seanwalsh1984
    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?

    • one year ago
  5. Tomas.A
    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

    • one year ago
  6. seanwalsh1984
    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!

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.