Learning objective
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).
Read the explanation, check the common trap, then practise with flashcards and questions.
At a glance
0
Flashcards
0
Questions
Topic
Regular languages
Subtopic
Finite state machines (FSMs) with and without output
Aqa A Level Computer ScienceTheory of computation
Study support
Understand this objective
Quick explanation
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)
- This point belongs to Regular languages, especially Finite state machines (FSMs) with and without output.
- You need to be able to 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).
- Use the linked flashcards and practice questions to check recall, then practise applying the idea in an exam-style answer.
Why it matters
This objective helps connect Finite state machines (FSMs) with and without output to exam-style questions, flashcards, and revision notes for Regular languages.
Quick student answer
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?
Direct answer
B
Key terms
- State transition: The change from the current state to a next state caused by an input.
- Mealy machine: A finite state machine with output, where the output is associated with the transition taken.
Common trap
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.
Related questions
Try this as a practice card
Question 1 of 4
Choose an answer, get feedback, then move sideways through the set.
0 of 4 attempted
Flashcard prompts
Flip through the key recall cards
Flashcard 1 of 4
Press Space to flip, arrows to move
Revision tools
Choose how to practise
Flashcards0 linked cards
No objective-specific flashcards are cached for this page. Use the topic hub to revise the surrounding flashcards without triggering a frozen-subject DB fallback.Open topic hub
Practice Questions0 linked questions
No objective-specific practice questions are cached for this page. Use the topic question bank to practise nearby curriculum questions without weakening the egress guard.Open topic questions
Related learning 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}
Maths for regular expressions
- 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 expressions
- 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.
Regular language