Explanation Given information: All United States social security numbers (which consistof three digits, a hyphen, two digits, another hyphen, and finally four more digits), where the final four digits start with a 3 and end with a 6. Calculation: Given: All social security numbers where the final four digits start with a 3 and end with a 6. A social security number contains 3 digits, followed by a hyphen-, followed by 2 digits, followed by a hyphen- and ending with 4 digits. Let [ 0 − 9 ] represent all digits 0 , 1 , 2 , 3 , 4 , 6 , 7 , 8 , 9 . Let us design an automaton with 13 states s 0 , s 1 , ... , s 12 where s 0 is the initial state. We draw each of the states as a circle with the name of the state within the circle. We draw an arrow towards the initial state and draw a second circle within the accepting states. s 0 = Initial state s 1 = Input has one digit s 2 = Input has two digits s 3 = input has three digits s 4 = Input has three digits, followed by a hyphen s 5 = input has three digits, followed bya hyphen, followed ba a digit s 6 = Input has three digits, followed by a hyphen, followed by 2 digits s 7 = Input has three digits, followed by a hyphen, followed by 2 digits, followed by a hyphen s 8 = Input has three digits, followed by a hyphen, followed by 2 digits, followed by a hyphen, followed by a 3 s 9 = Input has three digits, followed by a hyphen, followed by 2 digits, followed by a hyphen, followed by a 3, followed by one digit s 10 = Input has three digits, followed by a hyphen, followed by 2 digits, followed by a hyphen, followed by a 3, followed by two digits s 11 = Input has three digits, followed by a hyphen, followed by 2 digits, followed by a hyphen, followed by a 3, followed by two digits, followed by a 6 s 12 = Remaining inputs We then note that the state s 11 corresponds with inputs that are social security numbers where the final four digits start with a 3 and end with a 6, thus s 11 is the accepting state

5th Edition

ISBN: 9781337694193

Author: EPP, Susanna S.

Publisher: Cengage Learning,

See similar textbooks

Videos

Question

Chapter 12.2, Problem 45ES

To determine

To design a finite-state automaton to accept the language defined by the regular expression.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 12.2, Problem 44ES

Chapter 12.2, Problem 46ES

Students have asked these similar questions

i) Consider the set S = {−6, −3, 0, 3, 6}. Draw a graph G whose set of verti- ces be S and such that for i, j ∈ S, ij ∈ E(G) if ij are related to a rule that t'u you choose to apply to i and j. (ii) A graph G of order 12 has as a set of vertices c1, c2, . . . , c12 for the do- ce configurations of figure 1. A movement on said board corresponds to moving a coin to an unoccupied square using the following two rules: 1. the gold coin can move only horizontally or diagonally, 2. the silver coin can move only vertically or diagonally. Two vertices ci, cj, i̸ = j are adjacent if it is possible to move ci to cj in a single movement. a) What vertices are adjacent to c1 in G? b) Draw the subgraph induced by {c2, c6, c9, c11}

2. Find the exact value of 12 + 12+12+√√12+ √12+ 12

he following contingency table details the sex and age distribution of the patients currently registered at a family physician's medical practice. If the doctor sees 17 patients per day, use the binomial formula and the information contained in the table to answer the question: SEX AGE Under 20 20-39 40-59 60-79 80 or over TOTAL Male 5.6% 12.8% 18.4% 14.4% 3.6% 54.8% Female 2.8% 9.6% 13.2% 10.4% 9.2% 45.2% TOTAL 8.4% 22.4% 31.6% 24.8% 12.8% 100.0% if the doctor sees 6 male patients in a day, what is the probability that at most half of them are aged under 39?

Chapter 12 Solutions

Discrete Mathematics With Applications

Ch. 12.1 - If x and y are strings, the concatenation of x and...Ch. 12.1 - Prob. 2TY Ch. 12.1 - Prob. 3TY Ch. 12.1 - Prob. 4TY Ch. 12.1 - Prob. 5TY Ch. 12.1 - Prob. 6TY Ch. 12.1 - Prob. 7TY Ch. 12.1 - Use of a single dot in a regular expression stands...Ch. 12.1 - Prob. 9TY Ch. 12.1 - If r is a regular expression, the notation r +...

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

To design a finite-state automaton to accept the language defined by the regular expression.

Solution Summary: The author explains how to design a finite-state automaton to accept the language defined by the regular expression.

Videos

To design a finite-state automaton to accept the language defined by the regular expression.

Want to see the full answer?

Chapter 12 Solutions