Steps to draw a DFA (or NFA) from a simple statement?
I am given a simple statement: Construct a DFA over alphabet {0, 1} that accepts all the strings that end in 101?
My question is that what will be the steps to design it? Or design an NFA, because then I know the clear steps yo convert an NFA to a DFA, so I will then convert the NFA to the DFA.
Note:- It is just a minor course for me, so I have never studied anything like regular expressions, or any algorithms probably used to construct DFA's.
If you want more of an explanation on how I derived this, I'd be happy to explain, but for now I just drew the DFA and explained each state.
Sorry about the screenshot...I didn't know how to convert it straight to an image.
On input 0 at state 0, it loops back to itself. On 1, it prepares itself to end because it could possibly be '101'.
q1 loops to itself on input 1 because it's still preparing to end on '101'. Input '0' on q1 means it is preparing for input '10', so it goes to q2.
Input '0' on q2 breaks the whole cycle and goes back to q0. Input '1' results in moving to q3, the accepting state.
Any input on q3 results in going back to whatever point in the cycle the input corresponds with.
That is, on '1' it goes back to q1, or the state where the first '1' was encountered in '101', preparing to end.
On '0', it goes to q2 because in order to get to q3, there must have been an input of '1' from q2, so no matter what, the last two input symbols are '10' now.
- Return elements from a list that match a pattern
- convert/compile regular expressions to C code
- How to make the regex negative lookbehind consume discarded text?
- Generate words that fit in Guids (just for fun)
- Insert newlines before sequences of all-caps words
- Convert all uppercase words in a string to title case
- Add a character in between regex
- RegExp testing fails when string is validated in RegExp tools
- VSCODE snippet PHP to fill namespace automatically
- Regular expression to extract text between square brackets & last string out of the square bracket
- What is the difference between a plus and a star in regex?
- Extract class names from JAR with special formatting
- How to replace a comma with a dot in a number (or any replacement)
- regex to match at certain string and not followed by another string using notepad++
- RegEx for matching UK Postcodes
- Why does the grep command select more than expected?
- Regex for ISO 8601 durations
- Regular expression for number with length of 4, 5 or 6
- Regex to match a whole number not ending in some digits
- Can anyone lead me to DEFINE assertions documentation for regular expressions?
- Regex to find string not followed by separator and 1 or 2 digits
- Regex for quoting unquoted XML attributes
- Regex to extract all the rows from CSV - Apache Nifi
- 12-digit regex for phone number
- regex to exclude lowercase only strings, but save strings which contain capital
- Extract year with an optional plus right after from a string using PHP regex
- missing quotation marks on keys in JSON
- Regex for a valid hashtag
- Enumerate Possible Matches of Regular Expression in Java
- camelCase to underscore in vi(m)