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.
Chapter 51:
A = {1, 2, 3, 4, 5}, B = {1, 3 ,5, 7, 9}
What is A∩B?
A∩B = {1, 3, 5}
Chapter 51:
A set with all members of either set A or set B is a Union.
A set with all members of both set A and set B is called an Intersection.
What is it Called when you have all members of set A that are not in set B?
Difference.
A\B OR A-B.
Chapter 51:
A = {1, 2, 3, 4}, B = {1, 3, 5}
What is A\B?
A\B = {2,4}
Chapter 52:
What are Regular Expressions?
Tools that enable Programmers and Computers to work with text patterns.
Chapter 52:
What are the 4 most common Regular Expressions?
Vertical Bar Separates Alternatives.
? Question Mark indicates that there are 0 or 1 of the preceding element.
* Asterisk indicates that there are 0 or more of the preceding element.
⁺ Superscript Plus sign indicates that there is one or more of the preceding element.
Chapter 52:
What is a Regular Language?
A Language represented by a Regular Expression.
A Language that a Finite State Machine can accept.
