4.4 (every spec covered) Flashcards
(84 cards)
What is a set in the context of regex
an unordered collection of values in which each value occurs at most once.
A language is regular if it can be represented by
- A regular expression
- A Finite State Machine
What does a.e mean in regex
Matches any word that starts with a and ends with e
what does ^Hello mean
Matches any line that starts with Hello
What are regular expressions
Special sequences of characters that can be used to find or match patterns in text
If there is no symbol between symbols what does that mean
Members side by side must appear in that sequence
What does the pipe symbol mean|
Separates alternative options
What does the symbol * mean in context of regex
Indicates that there are zero or more of the preceding element
What does the symbol + mean in the context of regex
Indicates that there is one or more of the preceding elements
What does the symbol ? mean in the context of regex
Indicates that there are zero or one of the preceding element.
What does () symbol mean in the context of regex
Used to identify groupings
An 01 pair repeated any number of times
How is it represented in regex
(01)*
In the context of set comprehension
A = { x | x ∈ N ^ x != 0 }
define the variables
A represents the set
{}: This denotes a set. Sets are collections of distinct elements.
x: A variable that represents the elements of the set.
∣: The vertical bar is read as “such that” or “where”. separates the variable from the condition that the elements must satisfy.
natural numbers (N)
∈ = “is an element of”
What is a turing machine
A computer with a single fixed program expressed using:
A finite set of states in a state transition diagram.
A finite alphabet of symbols.
An infinite tape with marked off squares.
A sensing read-write head that can travel along the tape, one square at a time.
A⊆B
A is a subset of B
A⊂B
A is a proper subset of B
Difference between subset and proper subset
A is a proper subset of B if every element in A is also in B, but B has at least one extra element not in A
A normal subset does’nt have to satisfy this last condition.
What is the cartesian product
The cartesian product of two sets A and B is the set of all ordered pairs (a,b)
Let’s say A = {1, 2} and B = {x, y}.
The Cartesian product of A and B would be {(1, x), (1, y), (2, x), (2, y)}.
What is cardinality and what is denoted by
Cardinality- It represents the count of distinct elements within a set.
|A|
In any one transition the turing machine can: (3)
Read the symbol on the tape.
Erase or write a new symbol on the tape.
Move the head left or right by a single machine.
What is Backus Nuar Form
What is a meta language
a formal notation used to describe the syntax rules of a language unambiguosly
A language that describes a language
Why does Backus Nuar form exist when there are RNF (2)
Because not every language or pattern can be represented as a regular expression
meta-languages such as BNF have been devised
In the context of BNF what does this symbol mean ::=
Is defined as
In the context of BNF what does this symbol mean |
Or
