# Math Help - algorithm Question

1. ## algorithm Question

I need to figure out the answer to this question;

"Describe an algorithm that takes as input an automaton M = (Q,S, t, s,A),
where S = {a,b, c}, and determines whether or not M accepts a word a which does not
contain c (i.e. whether or not L(M) contains a word in {a,b}∗). You do not have to give
a formal proof that your algorithm is correct but you should indicate why this is the case."

This is what i ahve come up with so far, would you say this is correct?

Let M = (Q, S, t, s, A) be a fi nite deterministic automaton, where Q is
state set, S = a, b, c is alphabet, t : (Q x S) x Q) is transitions function,
s 'elem' Q is initial state, and A 'sub' Q is the set of nite state. To determine,
whether the word w 'elem' S* is accepted by M, do the following steps.

(a) If w = e (empty word), then w is accepted by M if and only if
t 'elem' A (initial state is also nite), process stops. Otherwise, go to
the next step.

(b) Let w0 = w, q0 = s, k = 0.

(c) If wk = e (empty word), then w is accepted by M if and only if
qk 'elem' A, process stops. Otherwise go to the next step.

(d) Let wk = xwk+1, where x 'elem' S (x is the first symbol of wk). Let
qk+1 = t(qk, x). Word w is accepted by M if and only if word wk+1
is accepted by automaton < Q, S, qk+1,wk+1 >.

(e) Increase k by 1, and go step c.

Each step reduces the length of current word (|wk+1| = |wk| - 1), so
this process is nite.

2. In your algorithm, w seems to be an input, whereas in the original problem, only M is the input. In other words, the problem is not this:

given M and w in {a, b}*, does M accepts w?

but this:

given M, does there exist a w in {a, b}* such that M accepts w?

3. Originally Posted by emakarov
In your algorithm, w seems to be an input, whereas in the original problem, only M is the input. In other words, the problem is not this:

given M and w in {a, b}*, does M accepts w?

but this:

given M, does there exist a w in {a, b}* such that M accepts w?
Ok, so are you saying i have produced a solution to the wrong problem? (well mt understanding of the problem is wrong)

Sorry i am not to good at this!

4. I think so.

Suppose M is given. I think that to find if M accepts some word without c, one has to make an exhaustive search. One starts with the initial state and tries every possible path following transitions for the symbols a and b only. Each state has to be visited at most once. If eventually a final state is reached, the answer is yes.

To make it more precise, you can consider a specific way to perform an exhaustive search, for example, breadth-first search.

5. Originally Posted by emakarov
I think so.

Suppose M is given. I think that to find if M accepts some word without c, one has to make an exhaustive search. One starts with the initial state and tries every possible path following transitions for the symbols a and b only. Each state has to be visited at most once. If eventually a final state is reached, the answer is yes.

To make it more precise, you can consider a specific way to perform an exhaustive search, for example, breadth-first search.
Thanks, i think i understand what your saying, im a little lost now though.
What do you think to this?

Draw the state diagram for M. Look for all transitions labelled "c" and remove them from
the diagram. Now try to find a path from the initial state s to any state in A. If at least one
state in A is reachable, that means the string corresponding to the edges on that path is a
member of L(M). Since none of the transitions had a "c", then the word must consist only
of a’s and b’s, and therefore M accepts at least one word that does not contain a "c".
Otherwise, if no path exists from s to a state in A, then the language does not accept any
word that does not contain "c".

6. Yes, this is better. In fact, there is an algorithm to find reachable states on p. 93 of "Elements of the Theory of Computation" by Lewis and Papdimitriou (2nd ed.). If we modify it a little, we get the following.

Code:
if s is in A then output "yes" and stop
R := {s}
while there is a state p in R, x in {a, b} and a state q such that t(p,x,q) and q is not in R do
if q is in A then output "yes" and stop
add q to R
end while
output "no"
Here R stands for the (gradually built) set of states reachable from s.

7. Originally Posted by emakarov
Yes, this is better. In fact, there is an algorithm to find reachable states on p. 93 of "Elements of the Theory of Computation" by Lewis and Papdimitriou (2nd ed.). If we modify it a little, we get the following.

Code:
if s is in A then output "yes" and stop
R := {s}
while there is a state p in R, x in {a, b} and a state q such that t(p,x,q) and q is not in R do
if q is in A then output "yes" and stop
add q to R
end while
output "no"
Here R stands for the (gradually built) set of states reachable from s.
Thanks very much for your guidance!