Section 9: Regular Languages Flashcards
Chapter 50:
What does FSM stand for?
Finite State Machine.
Chapter 50:
What is a Finite State Machine that does not give an output, often referred to as?
Finite State Automaton.
Chapter 50:
*Who invented the idea of the Mealy Machine?
George Mealy.
Published a paper called “A Method for Synthesising Sequential Circuits” in 1955.
Chapter 50:
What is the idea of a Mealy Machine?
It’s a type of Finite State Machine that has an output that is determined by both the current state, and the current input.
Chapter 50:
What are some Applications of a Mealy Machine?
Traffic Lights, Vending Machines, Timers, Basic Electronic Circuits, Cipher Machines (Given a sequence of inputs, get a new sequence of outputs).
Chapter 51:
What is a set?
An unordered collection of values, or symbols, with no repeating data.
Chapter 51:
Create a set “A” of all prime numbers between 1 and 20.
A = {2, 3, 5, 7, 11, 13, 17, 19}
Chapter 51:
What are the two types of set?
Finite Sets (length is a natural number), Infinite Sets (length is not a natural number).
Chapter 51:
What is the length of a Finite Set called?
Cardinality.
Chapter 51:
What is the Cardinality of a Finite Set?
The number of elements in the set.
Chapter 51:
What are the two main types of infinite?
What makes them different?
Countable Infinite,
Uncountable Infinite.
Countable Infinite is what we usually think when we hear “infinite”. If you have the set {1, 2, 3, 4, …}, the ‘last’ number will be infinite. Between two elements in a countably infinite set, there is a finite number of elements.
Uncountable Infinite is where you can take any two elements of the set, and there will be infinite elements between them.
An example of Countable Infinite is the ‘last’ number in the set of Natural Numbers.
An example of Uncountable Infinite is the ‘last’ number in the set of Rational Numbers.
Chapter 51:
What does the following Set Comprehension notation mean?
B = { n^2 | n∈ℕ ∩ n<5 }
B is the set of n^2 "|" such that n∈ℕ n is a member of the Natural Number Set ∩ and n<5 n is less than 5
B = { 1, 4, 9, 16 }
or
B = { 0, 1, 4, 9, 16 } (including 0)
Chapter 51:
What are the first 4 elements of this Compact Representation notation set?
A = { 0^n 1^n | n }
A = { 01, 0011, 000111, 00001111, … }
Chapter 51:
How is the Cartesian product of two sets A and B written and spoken?
A x B
“A cross B”
Chapter 51:
What do the following symbols mean?
∈
∉
⊆
⊂
⊈
⊄
∈ left is a member of the set on the right.
∉ left is not a member of the set on the right.
⊆ left is a subset of right.
⊂ left is a subset of right, but is not equal to right. (“proper subset”)
⊈ left is not a subset of right or equal to right.
⊄ left is not a subset of right. (not “proper subset”)
Chapter 51:
The members of sets A and B can be “added together” with OR logic.
What is this idea called?
Union.
A∪B.
Chapter 51:
A = {1,3,5}, B = {3,4,8}
What is A∪B?
A∪B = {1,3,4,5,8}
Chapter 51:
When you have set A OR set B, this is called a Union.
What is set A AND set B called?
Intersection.
A∩B.
