4.4.2 Regular Languages 4.4.3 Context-free languages Flashcards
(31 cards)
What is a Finite State Machine?
A Finite State Machine does not have output it is an abstract representation used in designing computer systems and logic circuits
What is a State Transition Diagram?
Uses circles to represent the states that a system may be in and arrows to represent the transitions between states
1) Start state
2) Accept State
What is a mealy machine?
A mealy machine is a type of FSM with an output that are determined by both its current state and the current input
What is a State transition table?
A State transition table is an alternative way of representing an FSM in a tabular form
What is a Set?
1) A set is an unordered collection of values or symbols in which each value or symbol occurs at most once
How do you represent a set?
A = {1, 2, 3, 4, 5}
How do you represent an empty set?
1) {} (Curly Braces)
2) Ø
Use Set comprehension to define this set
A = {x | x ∈ ℕ ∧ x ≥ 1 }
1) A is equal to x such that x is a member of the natural numbers and x is bigger than or equal to 1
What is a finite set?
A set whose elements can be counted off by natural numbers up to a particular number
E.g. 10 is the 6th number in set a
A = {1,2,4,6,8,10}
What is the cardinality of a finite set?
The number of elements in the set
What is a countably infinite set?
A set that can be counted off by the natural numbers
What is a Cartesian product of sets?
1) Written as X and Y and 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
2) E.g. A = {1,3,5} B = {12,25,40}
C = {(1,12), (1,25), (1,40), (3,12), (3,25), (3,40) , (5,12), (5,25), (5,40)
What is an infinite set?
1) Can be countable or uncountable and is not finite
What is a subset?
1) A subset is where every member of one set is also a member of another set
2) A ⊆ B = Every member of set A is also a member of set B
What is a proper subset?
A proper subset is when a set is a subset of another set but is not equal to another set
What is a countable set?
A countable set is a set with the same cardinality (number of elements) as some subsets of natural numbers
What is membership?
The property of an element being within a set
What is Union?
A∪B is the set of things that belong to either A,A or B,b
What is Intersection?
A∩B The set of things that belong to both A,A and B,B
What is difference?
List of elements that are in set A but not in Set B denoted by
- A - B
- A / B
What is a Regular Expression?
1) A way of describing a set
2) Allows types of languages to be described in a convenient shorthand notation
3) E.g. a(aIb) * = {a, aa, ab, aaa, aab, aba, ….}
What is the relationship between the regular expressions and the FSM’s?
They are equivalent ways of defining a regular language
What does this metacharacter indicate?
ab*
1) Indicates that there are zero or more of the preceding element
2) In this case zero or more b’s
3) ab, ab , abb, abbb
What does this metacharacter indicate?
a+b
1) Indicates that there are one or more of the preceding element
2) ab, aab, aaab
