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

Generating sets based on a recursive language definition

  1. Feb 6, 2012 #1
    I've searched the internet and the forums for any help on this, but I cant seem to find a topic that details what the successive sets will contain. Here is an example question: (I have many HW problems like this, I just don't know where to start)

    Let L be the language over {a,b} generated by the following recursive definition
    basis: λ ∈ L
    recursive step: If w ∈ L then awbb is in L.
    closure: A string w ∈ L only if it can be obtained from the basis set by a finite number
    of applications of the recursive step.
    Part a. Give the sets L1; L2; and L3 generated by the recursive definition. Note that L0 = λ

    I get that The alphabet is {a,b}, Lo = the empty string, and if a string w is contained in L, then awbb is in L. But what does that mean for the next couple sets?

    I think L1 = {λ ,awbb} and then L2={λ , awbb, aawbbwbb}?

    Any help you could offer on this would be appreciated.
  2. jcsd
  3. Feb 7, 2012 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    I'm not an expert on this topic, but I don't think 'w' is intended to be a an element of the language. It is a variable. Since 'a' an element of the language then the rule that mentions 'awbb' allows you to say that 'aabb' is in the language. It also lets you say that 'abbb' is in the language. Is that what you meant by the notation 'awbb'?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook