0
$\begingroup$

Let $L$ an arbitrary regular language and

$\qquad L_2 = \{uav : uv \in L\}$.

Am I correct to say that this language is not regular by saying:

$L$ has an even number of $a$'s. So $u$ and $v$ have an even number of $a$'s. However, $uav$ will have an odd number of $a$'s so $L_2$ is not regular?

$\endgroup$
  • 1
    $\begingroup$ What have you tried and where did you get stuck? This is a rather simple exercise! $\endgroup$ – Raphael Oct 26 '17 at 10:24
  • 2
    $\begingroup$ No, your argument is bogus. Odd letter counts are not a non-regular feature on their own. $\endgroup$ – Raphael Oct 26 '17 at 10:25
  • $\begingroup$ Hint: think about finite automata. $\endgroup$ – Raphael Oct 26 '17 at 10:25
4
$\begingroup$

General approach if one wants to show that an operation on languages preserves regularity is to assume that the language $L$ is regular, and given as automaton/ expression/ grammar. Based on this representation build a new automaton/ expression/ grammar, and explain the new construct actually represents $L_2$.

For instance, we can do so using regular expressions. See the answer *Showing Regular Languages are closed under removal of rightmost character for a related solution.

Let $\iota$ be the operator that inserts a single occurrence of the symbol $a$ into a language. We can transform a regular expression for $L$ into a regular expression for $L_2$ by defining recursively

  • $\iota(\varnothing) = \varnothing$
  • $\iota(\varepsilon) = a$
  • $\iota(\sigma) = a\sigma + \sigma a$
  • $\iota(RS) = \iota(R)S + R\iota(S)$
  • $\iota(R+S) = \iota(R) + \iota(S)$
  • $\iota(R^*) = R^*\;\iota(R) \;R^* + a$

Alternatively, here is a proof using closure properties. We know that the regular languages are closed under intersection (with regular languages) and under morphisms and inverse morphsims.

Let $c$ be a new symbol. Let $\varphi: \{a,b,c\}^* \to \{a,b\}^*$ be the morphism that deletes copies of $c$. Thus $\varphi^{-1}$ is the mapping that inserts copies of $c$ at arbitrary positions. Let $\psi: \{a,b,c\}^* \to \{a,b\}^*$ be the morphism that maps $a,c$ to $a$ and $b$ to $b$ (so it only changes the occurrences of $c$ into $a$. Finally let $K$ be the language over $\{a,b,c\}$ of all strings that contain exactly one occurrence of $c$.

Then $L_2 = \psi(\varphi^{-1}(L)\cap M)$, and is regular whenever $L$ is regular. $\varphi^{-1}$ chooses the position of the extra $a$, $M$ verifies exactly one position was selected, and $\psi$ puts $a$ at the selected position.

$\endgroup$
4
$\begingroup$

This language is regular. Let $M$ be a DFA accepting $L$ and assume it has a single initial and final state. We can construct a NFA accepting $L_2$. We create two copies of $M$: $M_1$ and $M_2$. Let us denote the states of $M_1$ as $q_1, \dots, q_n$ and the states of $M_2$ as $p_1, \dots, p_n$. Note that these two DFA are isomorphic where $q_i$ corresponds to $p_i$. The initial state of the new automaton will be $q_1$, and its accepting state will be the accepting state of $M_2$ (so the accept state of $M_1$ is no longer an accept state, and the initial state of $M_2$ is no longer an initial state; in the new NFA, these are just normal states). Add new transitions $\delta(q_i, a) = p_i$ for each pair $(q_i,p_i)$. The resulting NFA accepts $L_2$. You can think over it to prove it accepts $L_2$; effectively, $M_1$ is reading the $u$ part of the input and $M_2$ is reading the $v$ part.

$\endgroup$
  • 2
    $\begingroup$ You may want to hold back on answering obvious homework dumps so as not to encourange undesirable posting behaviour. $\endgroup$ – Raphael Oct 26 '17 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.