3
$\begingroup$

In the book Introduction to Languages and the Theory of Computation, I'm reading section 2.6 on how to minimize the number of states in an FA.

I'm having trouble understanding a notation defined as $L_q$. Here's what the book says:

Suppose we have a finite automaton $M = (Q, \Sigma, q_0, A, \delta)$ accepting $L \subseteq \Sigma^*$. For a state $q$ of $M$, we have introduced the notation $L_q$ to denote the set of strings that cause $M$ to be in state $q$:

$$L_q = \{ x \in \Sigma^* | \delta^*(q_0, x) = q\}$$.

The first step in reducing the number of states of M as much as possible is to eliminate every state $q$ for which $L_q$ = $\emptyset$, along with transitions from these states. None of these states is reachable from the initial state, and eliminating them does not change the language accepted by $M$.

I tried looking at this automaton to try to understand this definition:

enter image description here

How can any of the states $1$ through $5$ be $L_q = \emptyset$ if I can find a string that can reach every state for this FA?

That is I can reach state $2$ with string $a$, and state $5$ with string $ab$, etc. Is this a correct way to approach this?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

You're right. There is no such state with $L_q = \emptyset$

The first step in the minimization algorithm is: "delete all nonreachable states".

Improve this answer
$\endgroup$
2
  • $\begingroup$ I thought so... I just got confused because I was doing one of the exercises, and all of the FAs given had no unreachable states, so I thought maybe I was misunderstanding the definition. $\endgroup$
    – badjr
    Feb 14, 2013 at 22:03
  • 2
    $\begingroup$ You weren't. If you look at the definition of FA, it is perfectly legal to have states that aren't reachable at all. That makes the definition simpler, while making no difference in the languages handled. $\endgroup$
    – vonbrand
    Feb 14, 2013 at 22:39
0
$\begingroup$

one more thing you can add is that , a state having $L = \emptyset$ cannot be reached from start state with any transition. hence if a state exists without being reached by start state then the language associated with that state is $\emptyset$ . further during dfa unless not specified for minimization such state does not exists

Improve this answer
$\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.