Theory of computationːRegular languages

From Wikibooks, open books for an open world
Jump to navigation Jump to search

PAPER 1 - ⇑ Theory of computation ⇑

Regular languages Finite state machines →


Regular Languages[edit | edit source]

  • Finite State Machines with and without Output (Mealy Machines)
  • Maths for Regular Expressions
  • Regular Expressions
  • Regular Languages
  • Backus-Naur Form for Context-Free Languages


Regular Expressions[edit | edit source]

A regular expression is an expressions used to specify a set of strings that satisfy given conditions (A sequence of characters that define a search pattern). They are used by programmers and computers to work with text patterns. The most popular implementations are in search engines and search & replace dialogues in word processors.


Most programming languages support regular expressions, but the most common symbols are described below:

  • | A vertical bar separates alternatives e.g. (D|d)is(c|k)
  • ? A question mark indicates zero or one of the preceding element e.g. colou?r
  • * An asterisk indicates zero or more of the preceding element e.g. aa and aabbb would match aab*
  • + A plus indicates one or more of the preceding element e.g. abc and abccc would match abc+


If your programming language supports regular expressions, such as Python, the syntax might be different.