State automaton are often used to represent electronic systems or controllers with limited memory involved. Some purposes might be dishwashers, thermostats, digital watches and calculators are all computers with limited memory.
Markov chains are Finite State Automatons probabilistic counterpart used when attempting to recognise patterns in data. These are used in speech processing, and in optical character recognition, or even predict price changes in financial markets.
you can't use one to detect strings that consist of n repeats of the letter "a" followed by n repeats of the letter "b". For those sort of patterns you need a more powerful system called a grammar (see the section on Parsing). But nevertheless, regular expressions are very useful for a lot of common pattern matching requirements.
It is not possible to express languages that represent palindromes. E.g. civic, radar, level, rotor, kayak, madam, and refer.
Checking an email address
Checking that a date entered is (somewhat) sensible
Checking that a date entered is guaranteed to be valid
Checking that a credit card number has 16 digits
You can't use one to detect strings that consist of n repeats of the letter "a" followed by n repeats of the letter "b". For those sort of patterns you need a more powerful system called a grammar (see the section on Parsing). But nevertheless, regular expressions are very useful for a lot of common pattern matching requirements.
It is not possible to express languages that represent palindromes. E.g. civic, radar, level, rotor, kayak, madam, and refer.
Note, with the credit card example, regular expressions are not suitable in telling you if the credit card is valid. What is the role of the regular expression? The role of the regular expression is to verify if an input string fits a particular pattern or "regular language". In checking if a credit card is valid one would need to compute the last digit of the credit card.
Can you represent aⁿ bⁿ with regular language? (where n is a constant that represents the number of occurrences of the character before it).
Compilers contain an element called a parser.
Parsing HTML
Parsing programming languages
Parsing XML
Can you represent aⁿ bⁿ with regular language? (where n is a constant that represents the number of occurrences of the character before it).
Yes you can!
E -> aAb
A -> aAb | ε
Try it out..
E.g. aaabbb
This fits in with
E -> aAb
E -> a aAb b [with rule E -> aAb
E -> aa aAb bb [with rule E -> aAb
E -> aaa ε bbb [with rule A -> aAb | ε
aaabbb
Formal languages come up in various areas of computer science, and provide invaluable tools for the computer scientist to reduce incredibly complex systems to a small description, and conversely to create very complex systems from a few simple rules. They are essential for writing compilers, and so are activated every time someone writes a program! They are also associated with automata theory and questions relating to computability, and are used to some extent in natural language processing, where computers try to make sense of human languages.