tags: systems, compiler design
Regular Expression
A regular expression is a set of characters that match to a set of strings, The regular expression itself is defined by the set of strings it matches against. The set is called the Language generated by the RegEx and is symbolized by .
The language that the regular expression defines what can be thought as the keywords of your language
The letters or symbols that are used in your programming language are part of a set called the Alphabet and it is symbolized by , they can be more than even normal letters or symbols, the only exception is which means empty string and is not part of the alphabet set. An element of the alphabet set is called a symbol.
Some regular expression operations
Finite Automata
Finite automata is way of expressing how the regular expression converts from the alphabet stream to tokens. It is a really simple graph that represents the transition from state to different state by getting an input character. In the end the automata is just a simple graph that either accepts or does not accept an input string.
Types of finite automata:
- Non-deterministic Finite automata
- Deterministic Finite automata
Finite automata example
This DFA represents the processing of input string that ends in 10, 101, or 1000 the RegEx for it is probably