edited by
246 views
0 votes
0 votes

Consider $\text{L =a b, a a, b a a}$
Which of the following string is $\text{NOT}$ in $\mathrm{L}^{*}$ ?

  1. $\text{baaaaabaaaaa}$
  2. $\text{abaabaaabaa}$
  3. $\text{aaaabaaaa}$
  4. $\text{baaaabaa}$
edited by

1 Answer

1 votes
1 votes
Given, $L = \{ab, aa, baa\}$

$L^0 = \{\epsilon\}$

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

$L^2 = L^1.L^1$ $=$ $\{abab, abaa, abbaa, aaab,aaaa, aabaaa, baaab, baaaa, baabaa\}$

..

$L^n$ = $3^n$ possible strings by arranging any of the 3 strings in $L^1$.

As we know,

$L^* = L^0$ $\cup$ $L^1$ $\cup$ $L^2$ $\cup$ $L^3$ $\cup$ $….$

Now, coming to options,
(B) abaabaaabaa = ab+aa+baa+ab+aa
(C) aaaabaaaa = aa+aa+baa+aa
(D) baaaabaa = ba+aa+ab+aa

Only, option (A) cannot be created using $L^*$.

Related questions

1 votes
1 votes
0 answers
2
admin asked Oct 23, 2022
898 views
Using $\text{'RSA'}$ algorithm, if $p=13, q=5$ and $e=7$. the value of $d$ and cipher value of $'6'$ with $(e, n)$ key are$7, 4$$7, 1$$7, 46$$55,1$
0 votes
0 votes
1 answer
4
admin asked Oct 23, 2022
317 views
Size and complexity are a part ofPeople MetricsProject MetricsProcess MetricsProduct Metrics