Results 1 to 7 of 7

Math Help - algorithm Question

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    6

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2010
    Posts
    6
    Quote Originally Posted by emakarov View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2010
    Posts
    6
    Quote Originally Posted by emakarov View Post
    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".
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2010
    Posts
    6
    Quote Originally Posted by emakarov View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with Euclid's algorithm question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 4th 2010, 10:50 AM
  2. Algorithm question
    Posted in the Math Topics Forum
    Replies: 8
    Last Post: August 5th 2009, 05:19 AM
  3. Euclidean algorithm question help
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 12th 2009, 01:41 AM
  4. Question on algorithm (Sorting)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 26th 2009, 08:35 AM
  5. Algorithm Question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 4th 2007, 03:29 AM

/mathhelpforum @mathhelpforum