Programmer's Guide To Theory - Finite State Machines
Written by Mike James   
Monday, 23 August 2021
Article Index
Programmer's Guide To Theory - Finite State Machines
Finite Grammars
Regular Expressions

Regular Expressions

Most computer languages have a regular expression facility that allows you to specify a string of characters you are looking for. There is usually an OR symbol, often |, so A|B matches A or B. Then there is a quantifier usually * which means zero or more. So A* means A, AA, AAA and so on or the null string. There are also symbols which match whole sets of characters. For example, \d specifies any digit, \w specifies any character other than white space or punctuation and \s specifies white space or punctuation. There are usually more symbols so you can match complicated patterns but these three enable you to match a lot of patterns easily. For example, a file name ending in .txt is specified as:


A file name ending in .txt or .bak as:


A name starting with A and ending with Z as:


and so on.

As already mentioned, regular expressions usually allow many more types of specifiers, far too many to list here. The key point is that a regular expression is another way to specifying a string that a finite state machine can recognize, i.e. it is a regular grammar and this means there are limits on what you can do with it. In particular, you generally can’t use it to parse a real programming language and there is no point in trying.

It is also worth knowing that the "*" operator is often called the Kleene star operator after the logician Stephen Kleene. It is used generally in programming and usually means "zero or more". For example z* means zero or more z characters.

Not in this extract but included in chapter

  • Other Grammars
  • Turing Machines
  • Turing Thinking



  • The finite state machine is simple and less powerful than other machines with unbounded storage such as the Turing machine.

  • Finite state machines accept sequences generated by a regular grammar.

  • Regular expressions found in most programming languages are a practical implementation of a regular grammar.

  • The pushdown machine is slightly more powerful than a finite state machine and it accepts sequences generated by a context-free grammar.

  • A full Turing machine can accept sequences generated by a phrase structured grammar.

  • The different types of machine and grammars form a hierarchy of increasingly complex languages.

  • Although a Turing machine is more powerful than a finite state machine, in practice all machines are finite state machines.

  • A Turing machine with a tape limited to n cells is equivalent to a finite state machine with snx where s is the number of symbols it uses and x is the number of states in its controller.

  • Even though Turing machines are an abstraction and do not exist, we tend to create algorithms as if they did, making no assumptions about resource limits. If we do think of resource limits they are afterthoughts bolted on to rescue our inherently unbound algorithms.

  • Algorithms that are unbounded are the pure thought of computer science.


A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.



  1. What Is Computer Science?
    Part I What Is Computable?
  2. What Is Computation?
  3. The Halting Problem 
  4. Finite State Machines
    Extract 1: Finite State Machines
  5. Practical Grammar
  6. Numbers, Infinity and Computation
    Extract 1: Numbers 
    Extract 2: Aleph Zero The First Transfinite
    Extract 3: In Search Of Aleph-One
    Extract 4: Transcendental Numbers ***NEW!
  7. Kolmogorov Complexity and Randomness
    Extract 1:Kolmogorov Complexity 
  8. Algorithm of Choice
  9. Gödel’s Incompleteness Theorem
  10. Lambda Calculus
    Part II Bits, Codes and Logic
  11. Information Theory 
  12. Coding Theory – Splitting the Bit
  13. Error Correction 
  14. Boolean Logic
    Part III Computational Complexity
  15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From 
  16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
  17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete 



To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.


What Is the Shift-Left Approach in DevOps?

The short answer is that it is a methodology that brings software testing into earlier stages of the software development lifecycle. We look at the importance of this new approach and how to impl [ ... ]

ICRA 2022 It's A Wrap

ICRA 2022, the flagship conference of the IEEE Robotics and Automation Society Conference took place in Philadelphia at the end of May. There were 8K participants from 97 countries with 4.7K of them a [ ... ]

More News





or email your comment to:


Last Updated ( Monday, 23 August 2021 )