Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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

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

share|improve this answer
    
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. –  badjr Feb 14 '13 at 22:03
2  
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. –  vonbrand Feb 14 '13 at 22:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.