0

Describe the set of strings that belong to the set A defined recursively as follows BASIC STEP: λ ∈ A, 1 ∈ A RECURSIVE STEP: If x ∈ A then 0x ∈ A and x0 ∈ A.

A is the set of all strings over alphabet {0, 1} that are consituted by a sequence of zeros followed by a sequence of ones or a sequence of ones by a sequence of zeros and where both sequences have the same number of elements.

Asfandyar Abbasi
  • 3
  • What is $\gamma$. And you so a sequence of $1$s after or before a sequence of $0$ are possible. How? You start with $1$ but I don't any step that allows any string with two $1$s. I just see you can have a single $\gamma$ or single $1$ followed and/or preceeded by any number of $0$s. – fleablood Dec 15 '17 at 00:19
  • " and where both sequences have the same number of elements" Why? You have 1 with zero 0s. Those aren't equal. You have 01 so you also hav 001 and 0001 so you have 00010 and 000100 which... you don't describe at all. – fleablood Dec 15 '17 at 00:20
  • Then my answer should be the sets {1,0},{0,1} and {0}? @fleablood – Asfandyar Abbasi Dec 15 '17 at 00:27
  • No. Just think it out. Draw pictures. Read Dan Brumleve's analogy of parked cars. You can have ... nothing... you can have "1" and whatever you have you can stick a 0 after it or you you can stick a 0 before it. Not sure how to give hints on insights but.. what can you get by recursively sticking 0s before or after a $1$ or ""? – fleablood Dec 15 '17 at 01:31

1 Answers1

1

You've got a few things wrong with your interpretation. Here's an analogy as a hint: the language is a parking lot and the elements are its states. It starts out empty, so that's a possible state. There is one guy who sometimes parks his red car there, but only if the lot is empty. Everyone else who shows up has a blue car and they park it at one of the ends of the row of other cars, or anywhere if the lot is empty.

Dan Brumleve
  • 17,796