Making NFA of Regex ^[a-zA-Z0-9]{3,16}$
I'm trying to make a NFA of regex ^[a-zA-Z0-9]{3,16}$. I've understood that this regex means the language will only accept strings of length 3 to 16 which may include a to z, A to Z or 0 to 9.
I've tried to make this but the main issue I'm facing is how I can make the condition that it can only go to final state if string length is 3 or 16 and gets discarded otherwise. Any help would be appreciated.
Here's my attempt in which you can see the (3,16) on state 5 which I think is not a valid way to draw a NFA.
Finite machine states do not have any auxiliary data. They are just a state, and all they can do is transit to another state using a fixed set of transition rules.
You can still count up to a known finite number; you just need one state for each possible value. But you cannot "count" in any normal sense of the word. You can't see if two subsequences are the same length, for example.
So to accept sentences of fixed length up to 16 you will need 16 states, not including the start state nor the "sink" state where you go when the input does not match. (Usually NFAs are not required to be complete, so the sink state is implicit; it is used for any input for which there is no transition.)
That means your NFA will look roughly like this:
As it happens, there is no non-determinism there, so it's also a DFA.
- How do I pass a variable into regex with Node js?
- How do I use regex in a SQLite query?
- Python RegEx: match words in a string only if they are not preceded by a specific character
- Regular expression that ignores HTML entities
- Allow access to page only from certain referrer
- Regex to match string containing two names in any order
- Matching boot times from log using sed -E
- Validate Bangladeshi phone number with optional +88 or 01 preceeding 11 digits
- Split address and numbers
- Using setCustomValidity stops input from validating
- Use dynamic (variable) string as regex pattern in dart
- Regular expression matching Android package name
- Replace commas not inside single quotes with an @ symbol
- Visual Studio Code Search and Replace with Regular Expressions
- Split string on commas not inside double quotes
- Replace inner letters inside words that start with and end with a specific letter with the same amount of a specific character
- regex for expression with one separator hyphen
- Extracting specific data from a string with regex and Powershell
- Parse datetime string in Ydm.His format
- Extract all words double wrapped in curly braces
- Parse dot-delimited video filename to extract show title, series number and episode number
- Split a string into words, preserving contractions but removing leading apostrophes from words
- Split string on pipes which are not between square braces
- Simple regex pattern for email
- How to extract filename without extension in Makefile
- Regex pattern containing backlashes causes failure in preg_replace()
- preg_replace() pattern starting with < and ending with > doesn't find HTML comments as intended
- Split a string on spaces and/or commas after a word which may be preceded by a small word
- How to convert split() to preg_split()?
- Parse a string without delimiters into a 2d array