0
$\begingroup$

I'm trying to work out a proof by construction that $L/a$ would be regular.

$a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be changed is the set of accepted states ($F$)

I came up with the following definition of $F'$ for the new

$F' = \{q ∈ Q | \delta(q, a) ∈ F\}$

Where $Q$ is the set of states (the same for both machines), and $\delta$ is the transition function (also the same for both machines). I believe this would make any state that has a transition to an accepting state in the first machine an accepting state in the second machine (including prior accepting states, if they have a self-loop).

Am I missing anything here? It seems suspicious to me that I would only need to modify the set of accepting states and not any other component.

$\endgroup$
  • $\begingroup$ Well, have you tried it on some examples to see if it seems to be correct on those examples? Have you tried to prove your answer correct? Those would be the usual first strategies to check your answer. $\endgroup$ – D.W. Sep 21 '19 at 17:19
1
$\begingroup$

This proof uses both construction and knowledge of closure properties of regular languages.

First, we know that regularity of languages is closed under the reversal operation, see proof of Thm. 4.2 here.

We can then define an operation named chop such that:

$$ \text{chop}(L)=\{w|aw \in L\}, \text{ where } a \in \Sigma, $$

We can construct an NFA for chop, which simply omits the first transition (hence removing the first character):

This NFA is incomplete, but is just for the sake of illustration

Therefore the regularity is closed under the chop operation.

Finally, observe that we can produce R/a operation using chop and reversal:

$$ L/a = (\text{chop}(L^{R}))^{R} $$

Hence L/a has been constructed using closure properties so must be regular.

Hope this helps!

Source: Formal Languages module, second year, BSc Computer Science University of Warwick.

Edit: capitalisation of first word.

New contributor
Ollie T is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

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.