TOC 1.3 (pp. 63-76) Regex
- Due Oct 6, 2021 by 11:59pm
- Points 15
- Submitting a file upload
- File Types pdf
Goal
Build a regex up from test cases and a dfa/nfa
Task
The end of this activity is to create a regex, but in this process show your work through three steps (below).
Symbols
The alphabet Σ includes { a-z A-Z 0-9 _ . @ }, not spaces.
The alphabet A is a subset of Σ that includes { a-z A-Z }
The alphabet N is a subset of Σ that includes { 0-9 }
The alphabet T is a subset of Σ that includes { a-z A-Z 0-9 }
Rules
- must be exactly one @ symbol
- before the @ symbol
- one or more symbols from T
- zero or more _, but if present, cannot be by itself, like _@foo.com
- if any . is present before the @
- at least one symbol from T before a .
- at least one symbol from T between a . and the @
- after the @ symbol, must be exactly one .
- before the .
- one or more symbols from T
- after the .
- two or more more symbols from A
Steps
1. Write out test strings that should accept in the rules above with complete coverage. This means that the boundaries of the rules should be tested, e.g. if you see "at least one symbol", you should have test strings of "a" and "aa" to test both conditions of (one and more than one).
2. Write out test strings that should reject in the rules above with complete coverage. In this try to make strings that pass all rules EXCEPT one, and reject all rules.
3. Draw/create a DFA/NFA for the rules above. Test your strings to validate it.
4. Convert your DFA/NFA to a GNFA (see lecture or p76).
5. Reduce your GNFA to a regex (see lecture or p76). You do not need to show every single state reduction, but make each reduction obvious. For example, if you have 3 states in a row, like A -> q1 -> B-> q2 -> C -> qaccept, it is ok to reduce all three states to one by circling it and writing ABC.
Submission
PDF only. Please turn in the assignment in Canvas.