My Explanation On The Automata Assignment

Here is my homework for Automata Theory.
Pardon me for not being able to use MSPaint efficiently. ^^

As far as I can remember, the homework was to convert an NFA diagram to a DFA diagram.

Here's the NFA diagram:


Using subset construction, I am able to determine the states and state transitions.

δ_D({q₀},a) = δ_N(q₀,a) = {q₁}

δ_D({q₀},b) = δ_N(q₀,b) = {q₂}

δ_D({q₁},a) = δ_N(q₁,a) = {q₃}

δ_D({q₁},b) = δ_N(q₁,b) = {}

δ_D({q₂},a) = δ_N(q₂,a) = {}

δ_D({q₂},b) = δ_N(q₂,b) = {q₄}

δ_D({q₃},a) = δ_N(q₃,a) = {q₃} U {q₆} = {q₃,q₆}

δ_D({q₃},b) = δ_N(q₃,b) = {q₃}

δ_D({q₄},a) = δ_N(q₄,a) = {q₄} U {q₆} = {q₄,q₆}

δ_D({q₄},b) = δ_N(q₄,b) = {q₄}

δ_D({q₃,q₆},a) = δ_N(q₃,a) ∪ δ_N(q₆,a) = {q₃,q₆} ∪ {} = {q₃,q₆}

δ_D({q₃,q₆},b) = δ_N(q₃,b) ∪ δ_N(q₆,b) = {q₃} ∪ {} = {q₃}

δ_D({q₄,q₆},a) = δ_N(q₄,a) ∪ δ_N(q₆,a) = {q₄,q₆} ∪ {} = {q₄,q₆}

δ_D({q₄,q₆},b) = δ_N(q₄,b) ∪ δ_N(q₆,b) = {q₄} ∪ {} = {q₄}

δ_D({},a) = {}, δ_D({},b) = {}

From the subsets above we can produce this DFA:


However, we can still simplify the DFA (above). I'm not sure about the rules in simplifying DFAs yet, so I hope this will suffice for now:


Please leave your comments if I'm wrong or if I had broken some rules.

Read More ..

The Pumping Lemma for Regular Languages

src: http://www.seas.upenn.edu/~cit596/notes/dave/pumping2.html
Here's what the pumping lemma says:

* If an infinite language is regular, it can be defined by a dfa.
* The dfa has some finite number of states (say, n).
* Since the language is infinite, some strings of the language must have length > n.
* For a string of length > n accepted by the dfa, the walk through the dfa must contain a cycle.
* Repeating the cycle an arbitrary number of times must yield another string accepted by the dfa.

The pumping lemma for regular languages is another way of proving that a given (infinite) language is not regular. (The pumping lemma cannot be used to prove that a given language is regular.)

The proof is always by contradiction. A brief outline of the technique is as follows:

* Assume the language L is regular.
* By the pigeonhole principle, any sufficiently long string in L must repeat some state in the dfa; thus, the walk contains a cycle.
* Show that repeating the cycle some number of times ("pumping" the cycle) yields a string that is not in L.
* Conclude that L is not regular.

Why this is hard:

* We don't know the dfa (if we did, the language would be regular!). Thus, we have do the proof for an arbitrary dfa that accepts L.
* Since we don't know the dfa, we certainly don't know the cycle.

Why we can sometimes pull it off:

* We get to choose the string (but it must be in L).
* We get to choose the the number of times to "pump."

Read More ..

Operations That Can Be Performed on Languages

Concatenation
L₁ . L₂ = L₁L₂ = {w ε Σ| w=xy for some x ε L₁ and y ε L₂}

Closure (pairing of elements)
examples:
L₁ = {a}
L₁* = {e,a,aa,aaa,aaaa,...}
L₂ = {aa, bb}
L₂* = {e,aa, bb,aaaa,aabb,bbaa,bbbb,...}
L₃ = 0
L₃* = {e}
(note: * is Kleene's Star and e represents empty)

Positive Closure Property
L⁺ = LL*
example:
L = {aa,bb}
L* = {e,aa,bb,aaaa,aabb,bbaa,bbbb,...}
L⁺ = {aa,bb,aaaa,aabb,bbaa,bbbb,...}
Elements of L are concatenated with the elements of L*.

Union
L = L₁ ∪ L₂
example:
L₁ = {a}
L₂ = {b}
L₁ ∪ L₂ = {a,b}

Intersection
L = L₁ ∩ L₂
example:
L₁ = {a,b}
L₂ = {b}
L₁ ∩ L₂ = {b}

Difference
L = L₁ - L₂
example:
L₁ = {a,b}
L₂ = {b}
L₁ - L₂ = {a}

Complement
~L = Σ* - L

Read More ..

Automata Theory Part 2

Three Kinds of Finite Automata:

Deterministic Finite Automata (DFA)
Each state has a transition for every symbol in the alphabet.

Nondeterministic Finite Automata (NDFA)
States of an automaton of this kind may or may not have a transition for each symbol in the alphabet, or can even have multiple transitions for a symbol. The automaton accepts a word if there exists at least one path from q₀ to a state in F labeled with the input word. If a transition is undefined, so that the automaton does not know how to keep on reading the input, the word is rejected.


Nondeterministic Finite Automata, with ε Transitions
Besides of being able to jump to more (or none) states with any symbol, these can jump on no symbol at all. That is, if a state has transitions labeled with ε, then the NFA can be in any of the states reached by the ε-transitions, directly or through other states with ε-transitions. The set of states that can be reached by this method from a state q, is called the ε-closure of q.

Read More ..

Automata Theory Part 1

Automata theory is actually the study of abstract machines and problems which they are able to solve. Automata theory is closely related to formal language theory as the automata are often classified by the class of formal languages they are able to recognize.

An automaton is a mathematical model for a finite state machine (FSM). An FSM is a machine that, given an input of symbols, "jumps", or transitions, through a series of states according to a transition function (which can be expressed as a table).

The input is read symbol by symbol, until it is consumed completely. Once the input is depleted, the automaton is said to have stopped.

Depending on the state in which the automaton stops, the automaton either accepts or rejects the input (Final state or Dead state). If it landed in an accept state, then the automaton accepts the word. If, on the other hand, it lands on a reject state, the word is rejected. The set of all the words accepted by an automaton is called the language accepted by the automaton.

Automata play a major role in compiler design and parsing.

Vocabulary:
Symbol
An arbitrary datum which has some meaning to or effect on the machine.
Word
A finite string formed by the concatenation of a number of symbols.
Alphabet
A finite set of symbols. An alphabet is frequently denoted by Σ, which is the set of letters in an alphabet.
Language
A set of words, formed by symbols in a given alphabet. May or may not be infinite.

An automaton is represented by the 5-tuple , where:
* Q is a set of states.
* ∑ is a finite set of symbols, that we will call the alphabet of the language the automaton accepts.
* δ is the transition function, that is

δ:Q X ∑ -> Q.

(For non-deterministic automata, the empty string is an allowed input).

* q0 is the start state, that is, the state in which the automaton is when no input has been processed yet, where q0 is an element of Q.
* F is a set of states of Q (i.e. F is an imporper subset Q) called accept states.

Read More ..