World's most popular travel blog for travel bloggers.

How to read this inductive language definition?

, , No Comments
Problem Detail: 

A language $L$ is defined recursively according to the following rules:

  • $λ ∈ L$
  • If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$

I am not sure if strings from this language should mix from this definition. Would strings only consist of $bbbb$ and $aaaa$, or can it also consist of $bbaa$, $aabb$, and so on?

Asked By : Ducksauce88
Answered By : Yuval Filmus

The recursive definition implies that a word $w$ is in $L$ if there is a sequence $w_0,\ldots,w_n=w$ such that $w_0$ is the empty word and for each $i=1,\ldots,n$, either $w_i = bw_{i-1}$ or $w_i = w_{i-1}aa$. This, in turn, implies that $L = b^*(aa)^*$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback