Cheap and Secure Web Hosting Provider : See Now

[Solved]: How to find $L_q = \emptyset$, a state that is not reachable for any given string?

, , No Comments
Problem Detail: 

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?

Asked By : badjr

Answered By : Dan

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

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9781

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback