CMSC 28000 — Problem Set 2

Instructions

This problem set is due on Wednesday January 22, 2020 at 18:00, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

1. Let $L$ be a regular language. Show that the language $$+L = \{u \in \Sigma^* \mid \exists v \in \Sigma^*, uv \in L \}$$ is also regular.
2. Let $L$ be a regular language. Show that the language $$L_n = \{w \in L \mid |w| = n\}$$ is regular.
3. We define the insertion operation on two strings $x$ and $y$ by $$x \leftarrow y = \{x_1 y x_2 \mid \exists x_1,x_2 \in \Sigma^*, x = x_1x_2\}.$$ In other words, the insertion of $y$ into $x$ produces the set of words where $y$ has been inserted at each position of $x$. For example, $$cat \leftarrow dog = \{dogcat, cdogat, cadogt, catdog\}.$$ Then the insertion of a language $L_2$ into a language $L_1$ is $$L_1 \leftarrow L_2 = \bigcup_{x \in L_1, y \in L_2} x \leftarrow y.$$ Suppose $L_1$ and $L_2$ are regular and are accepted by DFAs $A_1$ and $A_2$, respectively. Construct an $\varepsilon$-NFA that accepts $L_1 \leftarrow L_2$ and informally explain how it works.