If L is a regular language, the language of subsequences of strings in L is also

Question

If L is a regular language, the language of subsequences of strings in L is also a regular language. Here we ask a related question. Let L and L Degree be regular languages on the same alphabet . We want to recognize Extseq(L Degree, L), the language of all strings in L that have some subsequence that is a member of L Degree. Show that when L Degree and L are regular, so is Extseq(L Degree, L). Show that the language of all strings in L that have no subsequence that is a member of L Degree is regular, whenever L and L Degree are regular.

Explanation / Answer

Alphabet E = {abc}

1) If L is regular language, the language of subsequences of string in L is also a regular language.

Assume L = {abaab*ca*ab}

+ = 1 or more; * = zero or more

which means L must start with abaab and then any number of b’s followed by a c, then any number of a’s (zero or more) followed by ab

L = ^[abaa][b*]c[a*]ab$

Valid strings for L = abaacab, abaabbbbbbbbcab, abaacab, abaabcaab, abaacaaaaaaaaaaab, abaacaaaaaaaaaaaaaaaaaaab, abaacaaaaaab, abaabbbbbbbbbbbcaaaaaaaaaaaaaaaaaaab

Invalid strings for L = not aba (because it is not ending with a b), etc

The subsequence or sub string L’ be = {baa}

L’ = ^[baa]$

Let Lo be = { abbac}

Lo = ^[abbac]$

Goal: We need to recognize ExtSeq(Lo , L), the language of all strings in L that have at least some

subsequence (sub string(s) ) that is a member of Lo .  

Let ES = ExtSeq(Lo , L) = all strings in L that have some substrings in Lo

Let LS = abaacab as it has the substring abbac in Lo

a). Hence it proved and shown that ES = ExtSeq(Lo , L) is regular as long as both L and Lo are also regular.

Valid strings for L = abaacab, abaabbbbbbbbcab, abaacab, abaabcaab, abaacaaaaaaaaaaab, abaacaaaaaaaaaaaaaaaaaaab, abaacaaaaaab, abaabbbbbbbbbbbcaaaaaaaaaaaaaaaaaaab, abaabc

(b) Showing that the language of all strings in L that have no

subsequence (sub strings) that is a member of Lo is regular, whenever L and

Lo are regular.

Lo = ^[abbac]$

Consider the string abaabc of L

This one does not have a substring in Lo as there is a b in between the a and c

But in spite of that L is regular and also is Lo regular

hence proved and shown that language of strings in L (abaabc) with no substrings in Lo is regular provided L and are Lo regular.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.