# showing that a regular language is regular after taking a letter off or after adding letters

I'll be happy to recieve help with this one:

Given the regular language $L$ defined over alphabet $\{a,b\}$, show that the following languages are also regular:

• $\{xy\mid xay\in L\}$ (meaning, taking one $a$ of the word in the middle)
• $\{x(a^*)y\mid xy\in L\}$ (meaning, adding in the middle of the word as much $a$'s as wanted)

-
If the question has been answered to your satisfaction, could you please indicate this by accepting an answer? (And preferably upvoting all answers you found helpful, as well.) –  Tara B Nov 17 '12 at 15:41

For the second problem, start with a right regular grammar for $L$. For each non-terminal symbol $X$ of $L$ add two new non-terminal symbols, $X'$ and $X''$. For each production of the form $X\to\alpha Y$ add the productions $X\to\alpha Y'$, $Y'\to aY'$, $Y'\to aY''$, and $X''\to\alpha Y''$. For each production of the form $X\to\alpha$ add the production $X''\to\alpha$. (Here $\alpha\in\{a,b\}$.) The idea is that the grammar starts out using the original non-terminals to generate the $x$ part of $xa^*y$, switches to one of the single-prime non-terminals to generate the $a^*$ part, and then generates the $y$ part using the double-prime non-terminals. It’s set up so that once it uses a primed variable, it can’t generate any of the original non-terminals, so it can generate an extra string of $a$’s only once.

You can use a similar idea for the first problem, though the details are a bit messier, and it’s easier to work with automata. Start with a DFA $M$ that accepts $L$; we’ll build an NFA $N$ that accepts the modified language. Start with two disjoint copies of $M$, say $M_1$ and $M_2$. The initial state of $N$ will be the initial state of $M_1$, and the acceptor states of $N$ will be the acceptor states of $M_2$. $M_1$ and $M_2$ will keep their original transitions. Finally, for every $a$-transition from a state $q_1$ to a state $q_2$ in $M_1$ we need an $\epsilon$-transition from $q_1$ in $M_1$ to the copy of $q_2$ in $M_2$. The idea is that we start in $M_1$ and proceed normally, except that at some point we follow one of those new $\epsilon$-transitions, simulating reading an $a$ and shifting over to $M_2$; then we continue just as if we were in the original $M$. The shift from $M_1$ to $M_2$ can happen only once, so we can delete only one $a$, and I’ve arranged matters so that we must delete one $a$ in order for the word to be accepted; how?

-
I don't study this material in english - what is a non-terminal symbol? thanks for the reply –  DanielY Nov 15 '12 at 21:49
@user1067083: The non-terminal symbols are the ones that are not part of the input alphabet. This article may help, even though it’s in English. –  Brian M. Scott Nov 15 '12 at 21:50
thanks alot for the answer for the first problem it was great!!! can you think of a NFA solution for the second as well? –  DanielY Nov 15 '12 at 21:52
add a state with a self $a$ transition in the middle of the $\varepsilon$-transitions you added –  Vincent Nivoliers Nov 15 '12 at 21:56
it's more than that I think, Vincent, because those a's can be added at any point in the word –  DanielY Nov 15 '12 at 21:59

Hint : imagine an automaton which recognizes the language L. Take a copy of this automaton, put it aside the original, add transitions between the two and select the right input and output nodes.

-

first part) Since L is a regular language, we can find a regular expression for it, and since we know that some of strings in L has symbol "a", the regular expression of L would be something like R1.a.R2+R3 where R1, R2 and R3 (R3 are the strings without "a") are regular expressions. since R1 and R2 are regular expressions, their concatenation would also be a regular expression. L(R1.R2)={xy∣xay∈L} so we could find a regular expression for {xy∣xay∈L}.

Second part can be answered similarly.

-
Wont work that easily. We might also want to insert a single $a$ in parts that are deep inside nested stars. –  Hendrik Jan Nov 16 '12 at 13:12