0
$\begingroup$

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

  • 0
    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.)2012-11-17

3 Answers 3

1

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?

  • 0
    ahh now I got it, thanks Vinc :)2012-11-15
0

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.

0

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.

  • 0
    Wont work that easily. We might also want to insert$a$single $a$ in parts that are deep inside nested stars.2012-11-16