Term
|
Definition
A finite automaton is a 5-tuple (Q, Σ, δ, q0, F) where
1. Q is a finite set called the states
2. Σ is a finite set called the alphabet
3. δ: Q x Σ -> Q is the transition function
q0 (exists in Q) is the start state
F (sub set of Q) is the set of accept states |
|
|
Term
| Machines ________ languages. |
|
Definition
|
|
Term
| Expressions _________ languages. |
|
Definition
|
|
Term
| The transition function (of a finite automata) can be represented as a ________. |
|
Definition
| Table. The coulmn headers are the input and the row headers are the states. The cross is the state to transition too given the input specified by each cells headers. |
|
|
Term
| What is required of a finite automata for ti to accept the empty string? |
|
Definition
| The start state to also be an accept state |
|
|
Term
|
Definition
| A U B = {x | x exists in A or x exists in B} |
|
|
Term
|
Definition
| A o B = {xy | x exists in A and y exists in B} |
|
|
Term
|
Definition
| A* = {x1x2...xk | k >= 0 and each xi exists in A) |
|
|
Term
| Are regular languages closed under union? Give the proof idea. |
|
Definition
Proof by construction. Two languages A1 and A2 that we know are regular. They are recognized by machines M1 and M2. Create a new machine M from M1 and M2. The states of M are a pair of states from M1 and M2. M accepts only if either M1 or M2 accepts.
Q = {(r1, r2) | r1 exists in Q1 and r2 exists in Q2}
Σ = Σ. Or Σ = Σ1 U Σ2
δ((r1, r2), a) = (δ1(r1, a), δ2(r2, a))
q0 = (q1, q2)
F = {(r1, r2) | r1 exists in F1 or r2 exists in F2}
--- Or with DFA, construct a new start state and give it an epsilon transition to the initial state of both machines. |
|
|
Term
| What is the difference in the definition of a DFA and a NFA? |
|
Definition
| In the transition function. In a DFA, the transition function takes a state and a symbol and produces the next state. In a NFA, the transition function takes a state and the input symbol (OR the empty string) and produces the set of possible states the machine could transition to. |
|
|
Term
| Every NFA has an equivalent DFA. Give the proof idea. |
|
Definition
Construct a DFA where each state corresponds to a set of states of the NFA. The machine has 2^k states.
Q' = P(Q)
δ'(R, a) = U δ(r,a) where R exists in Q' and r exists in R.
q0' = {q0}
F' = {R exists in Q' | R contains an accept state of the NFA} |
|
|
Term
| Are regular languages closed under concatenation? Give the proof idea. |
|
Definition
Regular language A1 and A2. Take NFA N1 and N2 accepting A1 and A2. Combine them into new NFA N.
Q = Q1 U Q2
q0 = q1 (Start state is the same as the start state of n1)
F = F2. Accept states are the same as N2
δ(q,a) = {
δ1(q,a) if q exists in Q1 and q does not exist in F1
δ1(q,a) if q exists in F1 and a is not epsilon
δ1(q,a)U{q2} if q exists in F1 and a = epsilon
δ2(q,a) if q exists in Q2 |
|
|
Term
| Are regular languages closed under the star operation? Give proof idea |
|
Definition
We have regular language A1. NFA N1 accepts A1. Create NFA N accepting A1*. Create new start state which is an accept state, with an epsilon transition to the original start state. Make all of the accept states have an epsilon transition back to the original start state.
Q = {q0} U Q1 (The states of N are the states of N1 plus a new start state)
The state q0 is the new start state
F = {q0} U F1 (The accept states are the old accept states plus the new start state)
δ(q,1) = {
δ1(q, a) if q exists in Q1 and q des not exists in F1
δ1(q,1) if q exists in F1 and a does not equal epsilon
δ1(q,a)U{q1} if q exists in F1 and a=epsilon
{q1} if q = q0 and a=epsilon
Empty Set if q=q0 and a!=epsilon
} |
|
|
Term
| Say that R is a regular expression if R is: |
|
Definition
1. a for some a in the alphabet Σ
2. epsilon,
3. empty set
4. (R1 U R2) where R1 and R2 are regular expression
5. (R1 o R2) where R1 and R2 are regular expressions
6. (R1*) where R1 is a regular expression |
|
|
Term
| What is the precedence of operaters in regular expressions? |
|
Definition
| Star, concatenation, then union. |
|
|
Term
| Define the Pumping Lemma for Regular Languages |
|
Definition
If A is a regular language, then there is a number p (the pumping length) where, if s is any substring in A of length at least p, then s may be divided into three pieces, s=xya, satisfying the following conditions:
1. for each i >= 0, xy^iz exists in A,
2. |y| > 0,
3. |xy| <= p |
|
|
