Sonoma State University
Department of Computer Science
CS-460: Programming Languages
Exercise 1b: Regular Expressions

Objective:

In a team of three or four students, define a regular expression that matches a C-style string including the encapsulating double quotes or encapsulating single quotes. Your regular expression should match escape characters within quoted strings as well (see the complete set of escape sequences below). I will supply paper for each group of students to create a deterministic finite state machine (DFA) diagram.

Strings and escape sequences to match:

In our C-like programming programming language, strings are encapsulated within double quotes or single quotes. The quotes - whether single quotes or double quotes - serve as delimiters to denote the beginning and ending of a string.

Examples:

• Double quotes used within a double-quoted string must be escaped. Example: "This string \" contains an escaped double-quote."
• Single quotes used within a single-quoted string must be escaped. Example: 'This string \' contains an escaped single-quote.'
• One or more unescaped single quote may be used within a double-quoted string. Example: "This string contains a bunch of 'unescaped' 'single' 'quotes' '''."
• An unescaped double quote may be used within a single-quoted string. Example: 'This string """ contains a bunch of "unescaped" "double" "quotes".'
• This double-quoted string contains a mixture of escaped characters: "This string contains a tab \t, a bell sound \a, and a newline character \n."
• This single-quoted string contains a mixture of escaped characters: 'This string contains a carriage return \r and a \x0 null character.'

The complete set of escape sequences is:

• \a: alert
• \b: backspace
• \f: formfeed
• \n: newline
• \r: carriage return
• \t: horizontal tab
• \v: vertical tab
• \\: backslash
• \?: question mark
• \': single quote
• \": double quote
• \xh: single digit hexadecimal number
• \xhh: double digit hexadecimal number

What should the deterministic finite state machine (DFA) look like?

• A non-final state should be represented by a single circle with a non-negative integer inside the circle.
• A final-state should be represented by two circles (one circle encapsulating a second circle) with a non-negative integer inside the inner circle.
• Each state (non-final or final) should use a unique non-negative integer that is not used for any other state in a given DFA.
• State transitions should be represented by arrows pointing from one state to another state. State transitions should include the byte which triggers the transition.

Submission Instructions:

On the sheet of paper, please write the names of each student in the group along with "Exercise 1b: Regular Expressions" then using an Android smartphone, iPhone, tablet, webcam, or digital camera take a digital photo of the completed diagram and upload to Canvas. I will collect the paper answers as well.

Exercise 1b Rubric

CRITERIA	RATINGS		POINTS
Deterministic Finite State Machine diagram	Proficient 10 points A partial or complete Deterministic Finite State Machine machine diagram is submitted which is relevant to the assignment guidelines above.	Below Expectation 0 points No solution submitted.	10 points
Total points: 10