Endelige språk og konkatenering
Posted: 30/08-2012 14:41
Har en oppgave jeg sliter litt med. Den er delt opp i a) og b).
"a) Consider the language L of all strings of a's and b's that do not end with b and do not contain the substring bb. Find a finite language S such that [tex]L = S^*[/tex]",
her er * Kleene-stjernen (i.e. alle konkatenasjoner (sammensetninger) av strengene i S).
Denne er i og for seg grei. Hvis vi lar [tex]S = \left{a, ba \right}[/tex] vil vi ha at [tex]L = S^*[/tex].
"b) Show that there is no language S such that [tex]S^*[/tex] is the language of all strings of a's and b's that do not contain the substring bb."
Her faller jeg litt av. Hva med språket i a)? Tilfredsstiller ikke det kravene? Hvorfor ikke?
"a) Consider the language L of all strings of a's and b's that do not end with b and do not contain the substring bb. Find a finite language S such that [tex]L = S^*[/tex]",
her er * Kleene-stjernen (i.e. alle konkatenasjoner (sammensetninger) av strengene i S).
Denne er i og for seg grei. Hvis vi lar [tex]S = \left{a, ba \right}[/tex] vil vi ha at [tex]L = S^*[/tex].
"b) Show that there is no language S such that [tex]S^*[/tex] is the language of all strings of a's and b's that do not contain the substring bb."
Her faller jeg litt av. Hva med språket i a)? Tilfredsstiller ikke det kravene? Hvorfor ikke?