0
$\begingroup$

I would appreciate some help for the following exercise:

$L$ is a regular language if and only if there is a "reduced" NFA $N=\langle Q,A,\Delta, q_0,F\rangle$ with $L=L(N)$.

With reduced I mean the following property: $\forall q \in Q \exists u, v \in A^* \exists q_f\in F : (q_0,u,q)\in \Delta$ and $(q,v,q_f)\in \Delta$

My problem is to show that there is such a NFA if $L$ is regular. I know I can assume that there is a NFA which accepts the language so my idea was to use the pumping lemma to construct a reduced NFA with it. Can someone give me a hint on how to approach this exercise?

$\endgroup$
1
$\begingroup$

What does $(q_0,u,q)\in \Delta$ mean?

It means that from the intial state you can reach this state.

What does $(q,v,q_f)\in \Delta$ mean?

It means that from the given state you can reach a final state.

If the first condition is not true, then the state is completely irrelevant, because it cannot be part of any computation. If the second condition is not true, then only computation that reject can pass through the given state; this kind of computation can be substituted by a computation that ends before entering this state, because there is no fitting transition.

So in either case, if we remove such a state and all transitions from and to it, all accepting computations are not affected, all rejecting computations still have equivalent ones.

This means that you can simply remove all states that violate the "reduced" condition. The resulting automaton is reduced and accepts the same language as the original one.

$\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.