Exercise 3.8
Prove or disprove each of the following assertions.
1.Every nonempty language contains a nonempty regular language.
TRUE
Every nonempty language (call it frodo) contains at least one item.
One item can be chosen from frodo (call it ‘a’).
a in sigma is a regular expression denoting the set {a}
let L1 = a L1 is a nonempty regular language that is a contained in frodo.
2.Every language with nonempty complement is contained in a regular language with nonempty complement.
TRUE
Suppose not, suppose there is a language with nonempty compliment (call it L1) that is NOT contained in a regular language with nonempty compliment (call it L2).
Let L2 = sigma* - (1 string (call it S1))
A DFA can be written that can filter out 1 string from sigma*, and sigma* can
Be represented with a DFA.
L2 is a regular language with nonempty compliment.
Now
If (L1 is contained in L2)
Contradiction QED
If (L1 is not contained in L2)
If (L1 is the language defined by S1)
L1 is contained in itself
L1 is defined by one finite string so it is regular and has a nonempty
Compliment.
Contradiction QED
If (L1 is not the language defined by S1)
If (L1 is sigma *)
Sigma* does NOT have a nonempty compliment (L1 must)
Contradiction QED
If (L1 is anything else)
L1 is not defined in this universe
Contradiction QED
In both the following definitions loop refers to one transition out of a state leading back into that same state. Loop does not refer to or include circular paths.
Exercise 3.10
Devise a general procedure that given some finite automaton M, produces the new finite automaton M’ such that M’ rejects epsilon, but otherwise accepts all strings that M accepts.
Make M into a DFA. This DFA is M’. Create a state (call it new_s) that has all the same out transitions of the start state in M’. Make this state new_s the new start state for the machine (M’). This state new_s is not an accept state.
A little added explanation about loops. Because new_s has ALL the same out transitions of the old start state in M’. If the old start state had a loop new_s will have a transition on that input symbol to the old start state.
Exercise 3.11
Devise a general procedure that, given a deterministic finite automaton M produces an equivalent deterministic finite automaton M’ (i.e., an automaton that defines the same language as M) in which the start state, once left, cannot be re-entered.
Call the start state of M start_s.
Create a state (call it new_s) that has all the same out transitions of the start state in M. Make this state new_s the new start state for the machine. If start_s was an accept state then new_s is an accept state. Make new_s the new start state.
A little added explanation about loops. Because new_s has ALL the same out transitions of the old start state in M. If the old start state had a loop new_s will have a transition on that input symbol to the old start state (start_s).
Exercise 3.24
A unitary language is a nonempty regular language that is accepted by a deterministic finite automaton with a single accepting state. Prove that, if L is a regular language, then it is unitary if and only if, whenever strings u, uv and w belong to L, then so does string wv.
Iff require a proof in each direction.
I know
There is one single accept state in this machine.
Since u is in the language.
There is a path u that goes from the start state to the (one) accept state. This path u terminates at the accept state.
(uv) is in the language, u terminates at the accept state so ( this is the key point) v must be a path from the accept state back to the accept state.
Suppose not
Suppose v started from some other state then the accept state.
Contradiction uv is accepted and u ends at the accept state
Suppose v did not end at the accept state
Contradiction uv is accepted, v must end at the accept state.
Since w is in the language.
There is a path w that goes from the start state to the accept state. This path w terminates at the accept state.
(wv) must be in the language since w is a path from the start state to the (one) accept state, and v is a path from the accept state back to the accept state.
QED
2. if L is regular and strings u, uv, w and wv belong to L then L is unitary
I know strings u, uv, w and wv belong to L.
Let w = uv
Now wv = uvv
Since a regular language is closed under concatenation uvv is in L.
Let w = uvv
Now wv = uvvv [ this can be done repeatedly]
Now w = uv*
v* is defined as
The same thing can be done with u by letting u = wv and you end up with u = wv*
The path uv is a path from the start state to (some) accept state that has the v* loop on it.
The path wv is a path from the start state to (some) accept state that has the v* loop on it.
Now uv and wv could end in two different accept states but this is just poor construction
They should end at the same accept state with the v* loop on it.
QED