Test 1 Flashcards
(32 cards)
What is an alphabet?
An alphabet is any non-empty finite set of symbols.
What is a string?
A string is a finite sequence of zero or more symbols.
The concatenation of two strings x and y is the string containing all the symbols of x in order, follwed by all the symbols of y in order.
T
What is a language?
A sequence over some fixed alphabet.
In a DFA, an arrow points to one of the states, the unique start state; double circles mark any number of states as accepting states.
T
If at an accepting state, we say that the machine…?
accepts the string.
What is it called when a string can’t reach the accepting state?
it is rejected.
What is the 5-tuple in symbol form?
M=(Q,Σ,δ,qsub0,F)
M = Q, Epsilon, Delta, q sub 0, F
The complement of a machine language is the reverse of the accepting states.
T
If “L” is any regular language, “L Complement” is also a regular language?
T
What are closed under complement?
Regular languages.
What is the product construction theorem?
If L1 and L2 are any regular languages, L1 intersect L2 is also a regular language.
If L1 and L2 are any regular languages, L1 union L2 is not a regular language.
F
For intersections, the new DFA accept when both the original DFAs accept.
T
Four unions, the new DFA accepts when?
Either or both of the original DFAs accept.
Whenever you prove something, you have to exercise judgment about how much to give.
T
The empty set is a legal alphabet.
T
The empty set {} = {e}.
F
The Kleene close of an alphabet is written how, and is the set of what?
E*(epsilon), all empty strings over E (epsilon).
Any and EVERY state transition diagram is a DFA.
F
What should be shown to make state transition diagrams fully specified?
Exactly one transition from every state.
“Q” often represents what?
A finite set of states.
Epsilon often represents what?
An alphabet.
Delta represents what?
(Q cross Epsilon)
