4.4.2 Regular Languages 4.4.3 Context-free languages Flashcards
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
What does this metacharacter indicate?
Dialog(ue)?
1) Indicates zero or one of the preceding element
2) Dialog, Dialogue
What does this metacharacter indicate?
DId)is(cIk
1) Indicates scope and precedence of the operators
2 ‘Disc’, ‘disc’, ‘Disk’ and ‘disk’
What does this metacharacter indicate?
Edward)I(Eddie)I(Ed
1) Boolean OR a vertical bar separates alternatives
2) Edward, Eddie, Ed
What can a language be called if it can represent a regular expression?
A regular language
What is a regular language?
Any language that a FSM can accept
What is the structure of Backus- Naur form (BNF)
1) LHS ::= RHS
2) ::== ‘is defined by’
3)
4) E.g. ::= 0I1I2I3I4I5I6I7I8I9
What is Parsing?
1) Determining whether a given statement is valid given the BNF definition
