Computer Science

Write a regular expression defining strings that begin with an a and end with a b and can contain any number (including zero) of c's or d's in the middle. Every c that is in the string must be followed by at least one d.

Construct a deterministic finite state automaton with no more than four states that accepts the language defined by the regular expression in problem 1.

  1. 👍 0
  2. 👎 0
  3. 👁 88
  1. Try
    my $pat="^ad*(cd+)*b\$"

    Use this pattern to match strings according to the rules specified.

    Note that $pat will match a qualifying string, but does not define a string.

    Hope someone else can answer the second part.

    1. 👍 0
    2. 👎 0
    posted by MathMate
  2. Explanation of the pattern follows:

    ^a specifies the string begins with "a"
    b\$ specifies that the string ends with "b"
    d* allows 0 or more embedded d's.
    (cd+)* requires a "c" to be followed by at least one "d". This can happen 0 or more times.

    1. 👍 0
    2. 👎 0
    posted by MathMate

Respond to this Question

First Name

Your Response

Similar Questions

  1. statistics

    What is your conclusion based on the following data? A survey was conducted to study the effects of weight loss from a low fat diet. Two random samples of 100 people each were selected. One group was put on the low fat diet and

    asked by jerry on June 22, 2013
  2. Math

    Find the $2 \times 2$ matrix $\bold{A}$ such that \[\bold{A} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \end{pmatrix}\] and \[\bold{A} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} -7 \\ 4

    asked by Zheng on February 25, 2017
  3. Chemistry

    Consider a saturated solution of calcium fluoride in 0.086 M potassium nitrate. Complete the following tasks, and then answer the question. a) Write the chemical equation corresponding to Ksp. b) Write the defining expression for

    asked by Ashley on October 7, 2012
  4. Math

    a. Write down a secret number, which can be any whole number Multiply by 5 Add 2 Multiply by 4 Add 2 Multiply by 5 Subtract 50 Drop the two zeros at the end. Do you recognize the result? B. Let S stand for a secret number that you

    asked by Kathy on October 29, 2010
  5. Pre Algebra

    During a sale, the regular price of a CD was reduced by $3. Let p represent the regular price of the CD. Write an algebraic expression that represents the sale price. Having trouble with this one, don't quite understand how to

    asked by Julio on September 3, 2017
  6. physics

    A ball of mass m = 500g moves around a vertical axis with an angular speed รน. It is attached to two strings of length: the upper a = 30 cm and the lower b = 40 cm.Both strings are taut and perpendicular to each other. Each of the

    asked by jamie on December 9, 2008
  7. geometry

    write an expression for the sum of the angle measures in a regular polygan with n sides. then wirte an expression for the measure of each angle in a regular polygan with n sides.

    asked by emily on April 19, 2010
  8. phy

    1. A Uniform rod AB 3m long weighing 3 Kg is held horizontally by two strong vertical strings at its ends. A weight of 7 kg is hanging on the rod at a distance of 1m from end A and another weight of 12 Kg is hanging at 0.5 m from

    asked by shiva on August 24, 2010
  9. physics

    a 1.29 kg ball is connected by means of two massless strings to a vertical, rotating rod. The strings are tied to the rod and are taut. The tension in the upper string is 38 N. The length of both strings is 1.70m and the distance

    asked by K on November 20, 2011
  10. Math

    Jane will receive 18% less of her regular pay when she retires. Her regular pay is $500 per week. a How much would she receive per week if she retires today? answer: 500/18% = 90 500-90= $410 b. Explain how you can make this same

    asked by John on March 26, 2015

More Similar Questions