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.
Chapter 52:
Which of the following strings are matched by the Regular Expression Sc(o⁺)(b|d)*y?
Scooby Scoby Scddy Scobby Scoobdbdbdy
Scooby Scoby S̶c̶d̶d̶y̶ Scobby Scoobdbdbdy
Chapter 53:
*Who was the creator of the Turing Machine?
Alan Turing (1912-1954).
He was interested in the question of computability; “Is every mathematical task computable?”
In 1936, he created the Turing Machine to answer this question.
Chapter 53:
What is a Turing Machine?
A Finite State Machine with an infinite input tape.
Chapter 53:
A Turing Machine has at least one state.
What is this state?
What does it do?
Halt State / Stop State.
Causes the program to stop for certain inputs.
Chapter 53:
What does the following Transition Function mean?
𝛿 ( S1, 0 ) = (S2, 1, L)
𝛿 means that it is a Transition Function.
If the current State is S1, and the input that is read is 0,
Then change the State to S2, change the write 1 to the location, and move left.
Chapter 54:
What is a “Natural Language”?
A language that is used in real world communication.
Examples: English, German, Korean, Russian…
Chapter 54:
What is a “Meta-Language”?
A language that details more than Regular Expression, but isn’t as ambiguous as a Natural Language.
Chapter 54:
What does BNF stand for?
What is it?
Backus-Naur Form.
It is a Meta-Language.
Chapter 54:
What is the structure of Backus-Naur form?
LHS ::= RHS
::= means “is defined by”
LHS is a meta-component (example: or )
Chapter 54:
What does the following Backus-Naur form mean?
::= 0|1|2|3|4|5|6|7|8|9
is a meta-component that can be 0 or 1 or 2… up to 9.
Question Broke
Question Broke
Chapter 54:
What is the name for the process of ascertaining whether a given statement is valid, given the BNF definition?
Parsing.
Chapter 54:
What is a Syntax Diagram?
Graphical method of representing the syntax of a meta-language, that maps directly to BNF.
(oval shape) Terminal Element (cannot be broken down further)
[rectangle] Non-terminal element (defined in another syntax diagram)
–[rectangle]– Non-terminal element that may be used more than once
L________I
Chapter 55:
- What is the other name for Polish Notation?
- Who invented it?
- When?
Prefix Notation.
Jan Łukasiewicz.
1924.
Chapter 55:
*What is the other name for Reverse Polish Notation?
Postfix Notation.
Chapter 55:
What are the advantages of using Reverse Polish Notation?
Eliminates the need for brackets.
Produces expressions in a form suitable for evaluation using a stack.
Unambiguous; computable.
Chapter 55:
What is the name of the Notation that we usually use for representing expressions?
Infix Notation.
Chapter 55:
Turn the following Infix Notation into Postfix Notation.
a*(b+c).
abc+*
Chapter 55:
What is the visual difference between Infix Notation and Postfix Notation?
Infix Notation - Operators are found between 2 values.
Postfix - Operators are found after 2 values.
Chapter 55:
How do you convert between Infix to Reverse Polish Notation?
Following this procedure on the Infix Notation left-right.
- Write first value.
- When you reach an operator, move up and make it central.
- Put the rest of the expression on the other branch from the operator.
- Split if needed; put the next value down and to the left of the current node.
This will create a tree.
Use Post Order Tree Traversal to get your Reverse Polish Notation.
Chapter 55:
How is Reverse Polish Notation evaluated using a stack?
Left to right on the RPN expression.
If you see a value, push it to the stack.
If you see an operator, pop the last 2 values from the stack, perform the operation on them, and push them back to the stack.
