edited by
11,694 views
35 35 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}$

4 Answers

Best answer
49 49 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
4 4 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:
Position:
Show:

Related questions

88 88 votes
15 answers 15 answers
32.7k
32.7k views
gatecse asked Aug 5, 2014
32,651 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...
15 15 votes
4 answers 4 answers
4.8k
4.8k views
gatecse asked Sep 29, 2014
4,826 views
Given the sequence of terms, $\text{AD CG FK JP}$, the next term is$\text{OV}$$\text{OW}$$\text{PV}$$\text{PW}$
17 17 votes
2 answers 2 answers
5.3k
5.3k views
gatecse asked Sep 29, 2014
5,300 views
Which one of the following options is the closest in meaning to the word given below?Mitigate DiminishDivulgeDedicateDenote
17 17 votes
2 answers 2 answers
5.1k
5.1k views
gatecse asked Sep 29, 2014
5,102 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 ...