Show that the family of regular languages is closed under exchange.
*22. The shuffle of two languages L 1 and L 2 is defined as
Show that the family of regular languages is closed under the shuffle
operation.
* 23. Define an operation minus5 on a language L as the set of all strings of L
with the fifth symbol from the left removed (strings of length less than five
are left unchanged). Show that the family of regular languages is closed
under the minus5 operation.
* 24. Define the operation left side on L by
Is the family of regular languages closed under this operation?
25. The min of a language L is defined as
Show that the family of regular languages is closed under the min
operation.
26. Let G 1 and G 2 be two regular grammars. Show how one can derive regular
grammars for the languages
(a) L (G 1 ) ∪ L (G 2 ).
(b) L (G 1 ) L (G 2 ).
(b) L (G 1 )*.
4.2 Elementary Questions about Regular Languages
We now come to a very fundamental issue: Given a language L and a string w,
can we determine whether or not w is an element of L? This is the membership