Topic study hub
Regular languages
Official AQA 7517 section 4.4.2.
0
Objectives
10
Flashcards
10
Questions
88 min
Study time
AqaA LevelComputer ScienceTheory of computation
Choose a revision tool
Start revising Regular languages
Syllabus checklist
What you need to know
0 objective pages available
Finite state machines (FSMs) with and without output1 objectives
- Finite state machines (FSMs) with and without output: Be able to draw and interpret simple state transition diagrams and state transition tables for FSMs with no output and with output (Mealy machines only).
Maths for regular expressions1 objectives
- Maths for regular expressions: Be familiar with the concept of a set and the following notations for specifying a set: A = {1, 2, 3, 4, 5 } or set comprehension: A = {x | x ∈ ℕ ∧ x ≥ 1 } where A is the set consisting of those objects x such that x ∈ ℕ and x ≥ 1 is true. Know that the empty set, {}, is the set with no elements. Know that an alternative symbol for the empty set is Ø. A set is an unordered collection of values in which each value occurs at most once. Several languages support set construction. In Python, for example, use of curly braces constructs a set: {1, 2, 3 }. | means such that. x ∈ ℕ means that x is a member of the set ℕ consisting of the natural numbers, ie {0, 1, 2, 3, 4, … }. The symbol ∧ means AND. The term ∧ x > = 1 means AND x is greater than or equal to 1. In Python, {2 ∗ x for x in {1, 2, 3 }} constructs {2, 4, 6 }. This is said to be a set comprehension over the set {1, 2, 3 }. Be familiar with the compact representation of a set, for example, the set {0n1n | n ≥ 1}. This set contains all strings with an equal number of 0 s and 1s. For example, {0n1n | n ≥ 1} = {01, 0011, 000111, 00001111, … } Be familiar with the concept of: • finite sets • infinite sets • countably infinite sets • cardinality of a finite set • Cartesian product of sets. A finite set is one whose elements can be counted off by natural numbers up to a particular number, for example as: 1st element, 2nd element, …, 20th (and final) element. The set of natural numbers, ℕ and the set of real numbers, ℝ are examples of infinite sets. A countably infinite set is one that can be counted off by the natural numbers. The set of real numbers is not countable. The cardinality of a finite set is the number of elements in a set. Cartesian product of two sets, X and Y, written X x Y and read 'X cross Y', is the set of all ordered pairs (a, b) where a is a member of A and b is a member of B. 58 Be familiar with the meaning of the term: • subset • proper subset • countable set. {0, 1, 2 } ⊂ ℕ where ⊂ means proper subset of, that is ℕ contains everything in {0, 1, 2 } but there is at least one element in ℕ that is not in {0, 1, 2 }. {0, 1, 2 } ⊆ {0, 1, 2, 3 } where ⊆ means subset of. ⊆ includes both ⊂ and =, for example {0, 1, 2, 3 } ⊆ {0, 1, 2, 3 } is also true, because {0, 1, 2, 3 } = {0, 1, 2, 3 }. A countable set is a set with the same cardinality (number of elements) as some subset of natural numbers. Be familiar with the set operations: • membership • union • intersection • difference. The set difference A\B (or alternatively A-B) is defined by A\B = {x: x ∈ A and x ∉ B}
Regular expressions1 objectives
- Regular expressions: Know that a regular expression is simply a way of describing a set and that regular expressions allow particular types of languages to be described in a convenient shorthand notation. For example, the regular expression a(a|b)* generates the set of strings {a, aa, ab, aaa, aab, aba, …}. Be able to form and use simple regular expressions for string manipulation and matching. Students should be familiar with the metacharacters: • * (0 or more repetitions) • + (1 or more repetitions) • ? (0 or 1 repetitions, ie optional) • | (alternation, ie or) • ( ) to group regular expressions. Any other metacharacters used in an exam question will be explained as part of the question. Be able to describe the relationship between regular expressions and FSMs. Regular expressions and FSMs are equivalent ways of defining a regular language. Be able to write a regular expression to recognise the same language as a given FSM and vice versa. A student's ability to write very simple regular expressions and FSMs will be assessed.
Regular language1 objectives
- Regular language: Know that a language is called regular if it can be represented by a regular expression. Also, a regular language is any language that a FSM will accept.
Key terms
State transitionMealy machineProper subsetCountably infinite setRegular expressionAlternationRegular languageFinite state machine (FSM)
Exam tips
- Trace one input at a time: For a sequence, write the current state, the input, the transition taken, the output if there is one, and the resulting state at every step.
- Translate notation before calculating: When given set-builder or compact notation, identify the condition on each element before listing or manipulating the set.
Common mistakes
- Putting Mealy outputs on states: For a Mealy machine, place or record the output on the transition, alongside the input, because the output is produced when that transition is taken.
- Treating a set as ordered: Remember that a set is unordered and each value occurs at most once. For example, writing an element twice does not create an additional distinct element.
Practice preview
- An FSM has states A and B. Its transition table is: from A, input 0 leads to B and input 1 leads to A; from B, input 0 leads to A and input 1 leads to B. If the FSM is in state A and receives input 0, what is the next state?
- A Mealy machine has a transition from state S to state T labelled 1/0. What do the two values mean?
- Which description identifies an FSM with no output rather than a Mealy machine?
Continue by objective
Objectives are grouped by subtopic so students can jump straight to the exact skill they want to revise.
Related topics