Generating sets based on a recursive language definition

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
1 reply · 3K views
nuguns
Messages
1
Reaction score
0
I've searched the internet and the forums for any help on this, but I can't 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.
 
Physics news on Phys.org
nuguns said:
I think L1 = {λ ,awbb} and then L2={λ , awbb, aawbbwbb}?

.

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 let's you say that 'abbb' is in the language. Is that what you meant by the notation 'awbb'?