2
$\begingroup$

A language is regular, if it is generated by a regular expression, meaning the expression consists of the alphabet $\Sigma_{\mathrm{RE}} = \Sigma \cup \{\epsilon, \varnothing, +,\ast,(, )\}$, and is formed only though union, concatenation and concatenation closure, as in

  1. $\mathcal L(\epsilon) = \{\epsilon\}$ is a regular language and $\epsilon$ the corresponding regular expression

  2. $\mathcal L(\varnothing) = \emptyset$ is a regular language and the symbol $\varnothing$ the corresponding regular expression.

  3. For every $\alpha\in\Sigma$, $\mathcal L(\alpha) = \{\alpha\}$ is a regular language and $\alpha$ the corresponding regular expression.

  4. For any two regular expressions $R$ and $S$, $\mathcal L(R + S) = \mathcal L(R) \cup \mathcal L(S)$ is a regular language and $R + S$ the corresponding regular expression.

  5. For any two regular expressions $R$ and $S$, $\mathcal L(R\ast S) = \mathcal L(R) \ast \mathcal L(S)$ is a regular language and $R \ast S$ the corresponding regular expression.

  6. The language $\mathcal L(R^\ast) = \mathcal L(R)^\ast$ is regular and $R^\ast$ the corresponding regular expression.

The language of prefixes is defined as $$ \operatorname{pre}\mathcal L = \{x \in \operatorname{pre} y \mid y \in \mathcal L\} \,. $$ If the language $\mathcal L$ is regular, show that $\operatorname{pre}\mathcal L$ is regular, using the above definition of regularity.

My current understanding

It seems to me that I would need to find out the prefixes of each language in the definition above, and then come up with a regular expression that generates them. So here are my thoughts:

  1. Since $\operatorname{pre}\epsilon = \epsilon$, we have $\operatorname{pre}\mathcal L(\epsilon) = \mathcal L(\epsilon) = \{\epsilon\}$

  2. Since $\operatorname{pre}\varnothing = \varnothing$, we have $\operatorname{pre}\mathcal L(\varnothing) = \mathcal L(\varnothing) = \emptyset$

  3. $\operatorname{pre}\mathcal L(\alpha) = \mathcal L(\alpha) = \{\alpha\}$ for all $\alpha\in\Sigma$, as $\operatorname{pre}\alpha = \alpha$.

  4. This is where it gets trickier. The language $$ \operatorname{pre}\mathcal L(R + S) = \operatorname{pre}( \mathcal L(R) \cup \mathcal L(S) ) = \{x \in \operatorname{pre} y \mid y \in \mathcal L(R) \cup \mathcal L(S) \}\,. $$ It looks like the regular expression $\operatorname{pre} R + \operatorname{pre} S$ would cover this part.

  5. Similarly to item 4, we have $$ \operatorname{pre}\mathcal L(RS) = \operatorname{pre}( \mathcal L(R) \mathcal L(S) ) = \{x \in \operatorname{pre} y \mid y \in \mathcal L(R) \mathcal L(S) \}\,, $$ so the regular expression $\operatorname{pre}(RS)$ looks appropriate.

  6. With the Kleene closure, $$ \operatorname{pre}\mathcal L(R^\ast) = \operatorname{pre}(\mathcal L(R)^\ast) = \{x \in \operatorname{pre} y \mid y \in \mathcal L(R)^\ast\}\,. $$ Here the regular expression $\operatorname{pre} R^\ast$ looks like it might work.

But I guess I still need to prove each of these. The first 3 items were obvious, but how do I show that the regular expressions actually generate the languages described?

$\endgroup$
5
  • 1
    $\begingroup$ Your points 1, 2, and 3 are all not quite right. Given a string $x$, $\operatorname{pre} x$ is a set of strings. Given a language $\mathcal{L}$, $\operatorname{pre} \mathcal{L} = \{x\in \operatorname{pre} y\mid y\in \mathcal{L}\} = \bigcup_{y\in \mathcal{L}} \operatorname{pre} y$. $\endgroup$ Mar 15, 2020 at 23:22
  • 1
    $\begingroup$ 1. $\operatorname{pre} \epsilon = \{\epsilon\}$, not $\epsilon$. Then $\operatorname{pre} \mathcal{L}(\epsilon) = \bigcup_{y\in \mathcal{L}(\epsilon)} \operatorname{pre} y = \operatorname{pre}\epsilon = \{\epsilon\} = \mathcal{L}(\epsilon)$. $\endgroup$ Mar 15, 2020 at 23:23
  • 1
    $\begingroup$ 2. $\operatorname{pre}\varnothing$. Here $\varnothing$ is a language (a set of strings), not a string. So we have $\operatorname{pre}\varnothing = \bigcup_{y\in \varnothing} \operatorname{pre} y = \varnothing$, i.e., $\operatorname{pre}\mathcal{L}(\varnothing) = \mathcal{L}(\varnothing)$. $\endgroup$ Mar 15, 2020 at 23:25
  • $\begingroup$ 3. $\operatorname{pre}\alpha = \{\epsilon,\alpha\}$, not $\{\alpha\}$. So $\operatorname{pre}\mathcal{L}(\alpha) = \bigcup_{y\in \mathcal{L}(\alpha)} \operatorname{pre} y = \operatorname{pre}\alpha = \{\epsilon, \alpha\} = \mathcal{L}(\epsilon)\cup \mathcal{L}(\alpha)$ is regular. $\endgroup$ Mar 15, 2020 at 23:26
  • $\begingroup$ @AlexKruckman I guess I was mixing up the prefixes of regular expressions with prefixes of languages. But wouldn't the former simply be the same thing as string prefixes, as regular expressions are strings? Or can we not call regular expressions strings, as they contain alphabets not in $\Sigma$? $\endgroup$
    – sesodesa
    Mar 17, 2020 at 13:58

1 Answer 1

5
$\begingroup$

I denote the regexp operator $+$ of union as $|$, and I omit the sign of composition $\circ$.

We are performing induction on the regular expression. The base cases are 1. 2. 3., but we get $\def\pre{\rm pre} \pre(\alpha)=\epsilon|\alpha$.

In what follows, we assume that $\pre(R)$ and $\pre(S)$ are already defined.

For 4., set $\pre(R|S):=\pre(R)\, |\, \pre(S)$.

For 5., set $\pre(RS):=\pre(R)\,|\, (R\, \pre(S))$.

For 6., set $\pre(R^*)=(R^*)\,\pre(R)$.


For a specific example, we have \begin{align} \pre\left((\alpha|\beta)^* \, \gamma\right) &= \left(\pre((\alpha|\beta)^*) \, \big|\, (\alpha|\beta)^*\, \pre(\gamma)\right) \\ &=\left((\alpha|\beta)^*\, \pre(\alpha|\beta)\, \big| \, (\alpha|\beta)^*\, (\epsilon|\gamma)\right) \\ &=\left((\alpha|\beta)^*\,( \pre(\alpha)\, |\, \pre(\beta))\, \big| \, (\alpha|\beta)^*\, (\epsilon|\gamma)\right)\\ &=\left((\alpha|\beta)^*\, ((\epsilon|\alpha)\, |\, (\epsilon|\beta))\, \big| \, (\alpha|\beta)^*\, (\epsilon|\gamma)\right) \,. \end{align} (which has nevertheless the same language as $(\alpha|\beta)^*(\epsilon|\gamma)$, so in specific examples the result of the above process might be 'simplified' by a shorter equivalent reg.exp).

$\endgroup$
8
  • $\begingroup$ What do I induce upon? I guess I should assume the regular expressions for parts 4--6 are the ones you gave, but for part 4 (as an example) should I then look at the regular expression $(R + S)\alpha = R\alpha + S\alpha$, where $\alpha\in\Sigma$, and then use the set properties of languages to show that this describes the language $\operatorname{pre}\mathcal L((R + S)\alpha)$? $\endgroup$
    – sesodesa
    Mar 17, 2020 at 14:26
  • 1
    $\begingroup$ A regular expression in your definition is built up inductively, just like e.g. first order formulas in logic, using some base cases (1., 2., 3.) and further operations (4., 5.,6.). Your example $(R|S)\alpha$ is primarily a composition, so 5. should apply there: $pre((R|S)\alpha)=pre(R|S) \, |\, (R|S) pre(\alpha)$, whence you can apply 4. and 3. to continue. $\endgroup$
    – Berci
    Mar 17, 2020 at 14:34
  • $\begingroup$ Right, so in each case I need to be able to reduce a more complicated expression into some combination of the base cases or parts of the definition. So I should assume the prefix of a union of languages is regular and then look at the case I just mentioned. $\endgroup$
    – sesodesa
    Mar 17, 2020 at 14:49
  • $\begingroup$ Yes, but also for the union, the induction hypothesis is that $pre(R)$ and $pre(S)$ are already expressed by a reg.exp, and then $pre(R|S)$ can be expressed as $(pre(R)) \, |\, (pre(S))$ $\endgroup$
    – Berci
    Mar 17, 2020 at 16:33
  • $\begingroup$ I've just come to realize that even though I used the notation, I'm not sure how the prefix of a regular expression such as $\operatorname{pre} R$ might be defined. I mean, we can't just take an arbitrary sequence of characters off the end of a regular expression such as $\alpha\beta(\gamma\delta)^\ast\varepsilon$, as that might leave us with an unpaired left parenthesis $($. $\endgroup$
    – sesodesa
    Mar 17, 2020 at 17:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .