0

how can I prove that if I have a regular language L and I create a new language L'

where L' = (L but with last letter repeated) (i.e. if ab is in language L then abb is in language L')

that L' is a regular language

I tried solving the question but I have no way of being sure of my solutions so I'll post it here:

L is a regular language therefor there is a regular expression for it, we create a new language x where x =L*($\Sigma$), $\Sigma$ is all the letters in language L ,x is a regular language because it is regular language chained with a letter ,and letters are a regular expression the language L' is a subset of x, there for x can be written as x=L' $\cup$ t (t=x/L'), and therefor L' has to be a regular expression because if it wasn't then x would not be a a regular language

J.-E. Pin
  • 40,163
Saher Amasha
  • 13
  • 1
    Welcome to MSE. You'll get a lot more help, and fewer votes to close, if you show that you have made a real effort to solve the problem yourself. What are your thoughts? What have you tried? How far did you get? Where are you stuck? This question is likely to be closed if you don't add more context. Please respond by editing the question body. Many people browsing questions will vote to close without reading the comments. – saulspatz Nov 30 '20 at 19:34
  • 1
    You've just written a list unproved assertions, many of which are untrue. In order to prove that the language is regular, you either have to produce a regular expression that generates it, a regular grammar that generates it, or an automaton that recognizes it. Now, my instinct is that the first two would be very difficult without a grammar or a regular expression of the original langue, but finding the automaton doesn't sound too bad. So, I suggest you try that. My best suggestion is, delete this question, work on the automaton, and if you get nowhere, ask a different question. – saulspatz Nov 30 '20 at 19:51
  • Check out this question: https://math.stackexchange.com/questions/75764/how-can-i-prove-that-this-language-is-regular?rq=1 – KingLogic Nov 30 '20 at 19:55
  • thanks ill check it out – Saher Amasha Nov 30 '20 at 19:57

2 Answers2

0

Since $L$ (over some alphabet $\Sigma$) is regular, there is a finite automaton $\mathcal{M}$ that recognises $L$. We now need to try and build a finite automaton $\mathcal{M}'$ that recognises $L'$. Let $Q_F$ be the collection of all state-symbol pairs of $\mathcal{M}$ that cause a transition into any of its accept states. More formally, $$Q_F := \{(q,s)\in Q\times \Sigma : \delta(q,s) \in F\}, $$ where $\delta\colon Q\times \Sigma \to Q$ is the transition function of $\mathcal{M}$, and $F$ is the set of accept states. We add a new state $A$ to $Q$ and make this the only accept state. Next, for every pair $(q,s)\in Q_F$, we add a new state $n_{(q,s)}$, and set $\delta^+(q,s) = \{n_{(q,s)}, \delta(q,s)\}$ and $\delta^+(n_{(q,s)},s) = A$. For $(q,s)\in (Q\times \Sigma) \setminus Q_F$ we leave $\delta^+(q,s) = \delta(q,s)$.

Note that the resulting automaton is non-deterministic, but this is fine since an equivalent DFA always exists. I now leave it up to you to show that this new NDFA $\mathcal{M}' := \{Q\cup A, \Sigma, \delta^+, q_o, A \}$ recognises $L'$.

Chubby Chef
  • 1,524
0

Let $A$ be the alphabet. For each letter $a \in A$, let $$ La^{-1} = \{u \in A^* \mid ua \in L\} $$ It is a well known fact that if $L$ is regular, then so is $La^{-1}$. Now your language $L'$ can be written as $$ L' = \bigcup_{a \in A}\ (La^{-1})aa $$ For each $a \in A$, $(La^{-1})aa$ is the product of the two regular languages $La^{-1}$ and $aa$ and this is regular. It follows that $L'$ is a finite union of regular languages and this is regular.

J.-E. Pin
  • 40,163