edited by
7,346 views
24 votes
24 votes

Given the language $L = \left\{ab, aa, baa\right\}$, which of the following strings are in $L^{*}$?

  1. $ abaabaaabaa$
  2. $ aaaabaaaa$
  3. $ baaaaabaaaab$
  4. $ baaaaabaa$
  1. $\text{1, 2 and 3}$
  2. $\text{2, 3 and 4}$
  3. $\text{1, 2 and 4}$
  4. $\text{1, 3 and 4}$
edited by

4 Answers

Best answer
36 votes
36 votes

   $L = \{ab,aa,baa\}$   

  1. $abaabaaabaa    =   ab  \ \   aa  \ \  baa \ \  ab \ \ aa$             belong to $L^*$ (combinations of strings in $L$ )
  2. $aaaabaaaa        =   aa \ \    aa \ \ baa \ \ aa$                       belong to $L^*$
  3. $baaaaabaaaab  = baa \  \ aa  \ \ ab  \ \ aa \  \ aa \ \ \mathbf{ b}$    does not belong to $L^*$
  4. $baaaaabaa        = baa \ \ aa \ \  ab \ \  aa$                        belong to $L^*$

Correct Answer: $C$

edited by
2 votes
2 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  

Answer:

Related questions

71 votes
71 votes
14 answers
1
gatecse asked Aug 5, 2014
18,998 views
What is the complement of the language accepted by the NFA shown below?Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.$\phi$$\{\epsilon\}$$a^*$$\{a , \epsilon...
9 votes
9 votes
4 answers
2
gatecse asked Sep 29, 2014
2,664 views
Given the sequence of terms, $\text{AD CG FK JP}$, the next term is$\text{OV}$$\text{OW}$$\text{PV}$$\text{PW}$
13 votes
13 votes
1 answer
3
gatecse asked Sep 29, 2014
2,795 views
Which one of the following options is the closest in meaning to the word given below?Mitigate DiminishDivulgeDedicateDenote
10 votes
10 votes
2 answers
4
gatecse asked Sep 29, 2014
2,939 views
Choose the most appropriate alternative from the options given below to complete the following sentence:Despite several _________ the mission succeeded in its attempt to ...