2

I'm having some difficulties solving an induction task.

Here is the task i'm working on:

Give an inductive definition of the given language below:

$\{(ab)^n\mid n\in\{0,1,2,\dots\}\} = \{\Lambda,ab,abab,ababab,...\}$

I'm very new to induction. What I dont understand is the statement above. what is $n$ and $(ab)^n$. I just can't figure out how i can solve a induction tasks like this. I would appreciate if you can tell me step by step on what to do to solve this task. I've tried to google on how to solve tasks like this, but with no luck really.

I hope I can get the help I need here.

Thanks alot!

Community
  • 1
Dabbish
  • 521
  • 2
  • 7
  • 15
  • 2
    That looks strange. ${(ab)^n\mid n\in{0,1,2,\ldots}}$ and ${\Lambda,ab,abab,ababab,\ldots}$ are two notations for the same language, so when you subtract one from the other you get the empty language. And certainly you could concoct an "inductive definition" of $\varnothing$, but not such that that there'd be any point in it. – hmakholm left over Monica Oct 12 '13 at 21:36
  • what if you only had the language ${(ab)^n\mid n\in{0,1,2,\dots}}$ would it still be an empty language then? – Dabbish Oct 12 '13 at 22:08
  • Um, of course not. But when you subtract it from itself, there'll be nothing left. – hmakholm left over Monica Oct 12 '13 at 22:11
  • okay thanks, but lets say we only have the notation ${(ab)^n\mid n\in{0,1,2,\dots}}$ How would you solve this notation then? If you could explain that to me I think i'll figure out the rest of the tasks. I think i was confused because of the second part – Dabbish Oct 12 '13 at 22:12
  • i think equal sign would be more correct in the middle of those two notations – Dabbish Oct 12 '13 at 22:21

1 Answers1

1

If you're looking just at the set $$ L = \{\Lambda,ab,abab,ababab, \ldots\}$$ then one possible inductive definition of $L$ might be something like:

  • The empty string is in $L$
  • Whenever $w\in L$ for some string $w$, then $wab$ is in $L$ too.
  • Nothing else is in $L$.

It is possible that in the particular context where you found the exercise, you're supposed to phrase the inductive definition in a particular formal way. For example, in certain context you might be expected to say,

$L$ is the least fixed point of the function $$ S \mapsto \{\Lambda\} \cup \{wab\mid w \in S \} $$

That depends a lot on context you have not given, though.

hmakholm left over Monica
  • 286,031
  • Thanks alot Henning! One small question. if you had the notation $L = {\Lambda,a,b,aa,bb,aaa,bbb}$ would the basis be ${\Lambda}$ and whenever w $\in$ $L$ for some string $w$, then $abw$ $\in$ $L$ too? Or i'm I wrong here? – Dabbish Oct 12 '13 at 22:40
  • @Dabbish: If you have a language consisting of only these 7 specific strings, then you wouldn't need induction at all. And you certainly couldn't use the same inductive definition, because that defines ${\Lambda,ab,abab,ababab,\ldots}$ which is not the same set as ${\Lambda,a,b,aa,bb,aaa,bbb}$. (For example, one contains $ab$, the other doesn't ). – hmakholm left over Monica Oct 13 '13 at 00:37