Results 1 to 2 of 2

Math Help - Formal Grammar and finite state acceptors

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    1

    Formal Grammar and finite state acceptors

    Hi I have been having some trouble with a question now for some time, could somebody help me out, I have come up with the following but I don't believe it is correct.

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    # Question

    (b)
    Give the specification of a finite state acceptor for the language L
    over the alphabet {p, q, r, s} consisting of all non-empty finite strings involving the
    letters p, q and r and s in which the letter p is always followed by the letter q and
    the letter r is always followed by the letter s. ln particular, you should specify the
    starting state, the finishing state or states, and the transition table for this finite
    state acceptor.

    ----------------------------------------------------------------------------------------

    is this correct ?

    +----+++-------------------+
    | -_ ||| P_ | Q_ | R_ | S_ |
    |----|||----|-----|----|-----|
    | S_ ||| T1 | T2 | T3 | T2 |
    | T1 ||| E_ | T2 | E_ | E_ |
    | T2 ||| T1 | T2 | T3 | T2 |
    | T3 ||| E_ | E_ | E_ | T4 |
    | T4 ||| T1 | F_ | T3 | F_ |
    | F_ ||| E_ | E_ | E_ | E_ |
    | E_ ||| E_ | E_ | E_ | E_ |
    +----+++----+----+----+----+

    ~~~~~~~~~~~~~~~~~~~~
    (c)
    Devise a regular grammar for part (b)

    ------------------------------------------------

    is this correct ?

    <S> -> P<A> | Q<C>| R<B>| S<C>
    <A> -> Q<C>
    <B> -> S<C>
    <C> -> P<A> | Q<C>| R<B>| S<C> | E
    <F> -> E


    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2009
    Posts
    23
    Jeez.Isn't the answer obvious?!?! Irish people eh?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 26th 2011, 12:53 PM
  2. Replies: 1
    Last Post: August 4th 2010, 03:39 PM
  3. Finite state and regular expressions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 27th 2009, 06:18 PM
  4. [SOLVED] Finite State Machine
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 3rd 2008, 10:13 PM
  5. finite state machines
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 9th 2006, 11:03 AM

Search Tags


/mathhelpforum @mathhelpforum