345 views
2 votes
2 votes
Let $L$={$ab,aa,baa$}.

Which of the following strings are in $L^*$ :

$abaabaaabaa$, $aaaabaaaa$, $baaaaabaaaab$, $baaaaabaa$? Which strings are in $L^4$?

2 Answers

0 votes
0 votes
given that L={ab,aa,baa}

than L* will be (ab+aa+baa)*

for 1st abaabaaabaa ->

=(ab+aa+baa)(ab+aa+baa)(ab+aa+baa)(ab+aa+baa)(ab+aa+baa)(ab+aa+baa)*

=ab.aa.baa.ab.aa.Epsilon=abaabaaabaa so it is in L* but not in L^4

similarly for others we can see

for 2nd aaaabaaaa

it is clearly in L* and L^4 also.

for 3rd baaaaabaaaab

it is not in L* and L^4

for 4th baaaaabaa

it is in L* as well as L^4.
0 votes
0 votes

Let $L$ be some language.

The closure of a language $L$ is denoted $L^*$ and represents the set of those strings that can be formed by taking any number of strings from $L$, possibly with repetitions (i.e., the same string may be selected more than once) and concatenating all of them.

So, a string $w$ belongs to $L^*$ iff $w$ can be broken into a sequence of substrings such that each substring belongs to $L.$ 

In more Formal Way, a string $w$ belongs to $L^*$ iff there is some integer $k \geq 0, $ such that $w = w_1w_2w_3 \dots w_k$ and each $w_i \in L.$

Moreover, a string $w$ belongs to $L^n$ iff $w$ can be broken into a sequence of $n$ substrings such that each substring belongs to $L.$

For example, a string $w$ belongs to $L^4$ iff $w$ can be broken into a sequence of $4$ substrings such that each substring belongs to $L.$

Now, we just need to check each string given in the question & see if we can break them into a sequence of substrings such that each substring belongs to $L.$

  1. $w_1 = \text{abaabaaabaa =}$  $\text{ab  aa  baa  ab  aa   }$  (This is the Unique breakup of $w_1$. So, $w_1 \in L^5$, Hence, $w_1 \in L^*$. BUT $w_1 \notin L^4$.) 
  2. $w_2 = \text{aaaabaaaa =}$  $\text{aa  aa  baa  aa   }$  (This is the Unique breakup of $w_2$. So, $w_2 \in L^4$, Hence, $w_2 \in L^*$. BUT $w_2 \notin L^5$.)
  3. $w_3 = \text{baaaaabaaaab =}$  $\text{baa  aa   ab  aa  aa   }  \color{red}{b}$  (Since we can’t break $w_3$ into a desired sequence of substrings, hence, $w_3 \notin L^*.$)
  4. $w_4 = \text{baaaaabaa =}$  $\text{baa  aa  ab  aa   }$  (This is the Unique breakup of $w_4$. So, $w_4 \in L^4$, Hence, $w_4 \in L^*$. BUT $w_4 \notin L^5$.)

NOTE: Since language $L$ is prefix-free (i.e. no string of $L$ is prefix of any other string of $L$), we will ALWAYS get an Unique breakup of every string $w \in L^*.$ 

$\color{red}{\text{Detailed Video Solution, with Complete Analysis:}}$ https://www.youtube.com/watch?v=PjoTWbeUygM&list=PLIPZ2_p3RNHhXeEdbXsi34ePvUjL8I-Q9&index=2  

Related questions

1 votes
1 votes
1 answer
2
0 votes
0 votes
2 answers
3