Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

Any direction to start with will be lovely Thank you

share|cite|improve this question
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
up vote 1 down vote accepted

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?

share|cite|improve this answer
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.

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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