with a regular language.
16. Show that if the statement “If L 1 is regular and L 1 ∪ L 2 is also regular, then
L 2 must be regular“ were true for all L 1 and L 2 , then all languages would be
regular.
17. The tail of a language is defined as the set of all suffixes of its strings, that
is,
Show that if L is regular, so is tail(L).
18. The head of a language is the set of all prefixes of its strings, that is,
Show that the family of regular languages is closed under this operation.
19. Define an operation third on strings and languages as
with the appropriate extension of this definition to languages. Prove the
closure of the family of regular languages under this operation.
20. For a string a 1 a 2 …a n define the operation shift as
From this, we can define the operation on a language as
Show that regularity is preserved under the shift operation.
21. Define
and