Regular Languages Flashcards
Finite state machine
A computational model which has a fixed number of potential states.
Two methods for representing a finite state machine
- State transition diagrams
- State transition table
Name given to finite machines where each input has a corresponding output?
Mealy machine
Set theory
mathematical logic in which sets are collections of objects
Set Comprehension
a collection of rules to define which values are in a set
Countable set
a set with the same number of values as a subset of the natural number N
Finite Set
a set with a fixed number of values
Infinite set
a set whose values go on forever
countably infinte set
values will go on forever but can still be counted
cardinality
the number of values in a finite ser
what is the cartesian product of A and B
A = {1,2}
B= {3,4}
A x B = { (1,3), (1,4), (2,3), (2,4)}
Regular expressions
a sequence of characters used to describe a pattern. Used in searching and validation
Syntax
a set of rules for a given language
production rule
the set of acceptable inputs for a given symbol
Permutation of set
the number of ways you can arrange the set if objects
