Finite Automata

       An automaton with a set of states, and its “control” moves from state to state in response to external “inputs”  is called a finite automaton.    

      A finite automaton, FA, provides the simplest model of a computing device. It has a central processor of finite capacity and it is based on the concept of state. It can also be given a formal mathematical definition. Finite automata are used for pattern matching in text editors, for compiler lexical analysis.

       Another useful notion is the notion of nondeterministic automaton.

       We can prove that deterministic finite automata, DFA, recognize the same class of languages as NDFA, ie. they are equivalent formalisms.

       It is also possible to prove that given a language L there exists a unique (up to isomorphism) minimum finite state automaton that accepts it, i.e. an automaton with a minimum set of states.

       The automata in the examples are deterministic, that is, once their state and input are given, their evolution is uniquely determined.

  

A deterministic finite automaton (or DFA) is a deterministic automaton with a finite input alphabet and a finite number of states. It can be formally defined as a 5-tuple (Sq0F)  , where

• S is a non-empty finite set of states,
• is the alphabet (defining what set of input strings the automaton operates on),
• :SS is the transition function,
• q0S  is the starting state, and
• FS is a set of final (or accepting states).

A DFA works exactly like a general automaton: operation begins at q0  , and movement from state to state is governed by the transition function . A word is accepted exactly when a final state is reached upon reading the last (rightmost) symbol of the word.
DFAs represent regular languages, and can be used to test whether any string in is in the language it represents. Consider the following regular language over the alphabet :=ab (represented by the regular expression aa*b):

<S> <A> ::= ::= aA b|aA  

This language can be represented by the DFA with the following state diagram:

The vertex 0 is the initial state q0  , and the vertex 2 is the only state in F . Note that for every vertex there is an edge leading away from it with a label for each symbol in . This is a requirement of DFAs, which guarantees that operation is well-defined for any finite string.
If given the string aaab as input, operation of the DFA above is as follows. The first a is removed from the input string, so the edge from 0 to 1 is followed. The resulting input string is aab. For each of the next two as, the edge is followed from 1 to itself. Finally, b is read from the input string and the edge from 1 to 2 is followed. Since the input string is now , the operation of the DFA halts. Since it has halted in the accepting state 2, the string aaab is accepted as a sentence in the regular language implemented by this DFA.
Now let us trace operation on the string aaaba. Execution is as above, until state 2 is reached with a remaining in the input string. The edge from 2 to 3 is then followed and the operation of the DFA halts. Since 3 is not an accepting state for this DFA, aaaba is not accepted.

Remarks.

• A DFA can be modified to include -transitionsEpsilonTransitions. But the resulting DFA can be simulated by another DFA (without any epsilon transitions).
• Although the operation of a DFA is much easier to compute than that of a non-deterministic automaton, it is non-trivial to directly generate a DFA from a regular grammar. It is much easier to generate a non-deterministic finite automaton from the regular grammar, and then transform the non-deterministic finite automaton into a DFA.

Types of Proofs

Proof by Construction  

       In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object. This is in contrast to a nonconstructive proof (also known as an existence proof or pure existence theorem) which proves the existence of a mathematical object with certain properties, but does not provide a means of constructing an example.

      Many nonconstructive proofs assume the non-existence of the thing whose existence is required to be proven, and deduce a contradiction. The non-existence of the thing has therefore been shown to be logically impossible, and yet an actual example of the thing has not been found. Nearly every proof which invokes the axiom of choice is nonconstructive in nature because this axiom is fundamentally nonconstructive. The same can be said for proofs invoking König's lemma.

      Constructivism is the philosophy that rejects all but constructive proofs in mathematics. Typically, supporters of this view deny that pure existence can be usefully characterized as "existence" at all: accordingly, a non-constructive proof is instead seen as "refuting the impossibility" of a mathematical object's existence, a strictly weaker statement.

Proof by Contradiction

       In logic, proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the proposition being false would imply a contradiction. Since by the law of bivalence a proposition must be either true or false, and its falsity has been shown impossible, the proposition must be true.

In other words, to prove by contradiction that P, show that  or its equivalent . Then, since  implies a contradiction, conclude P.

       Proof by contradiction is also known as indirect proof, apagogical argument, reductio ad impossibile. It is a particular kind of the more general form of argument known as reductio ad absurdum.

       The method of proof by contradiction is to assume that a statement is not true and then to show that that assumption leads to a contradiction. In the case of trying to prove  this is equivalent to assuming that  That is, to assume that P is true and Q is false. This is known by its latin reductio ad absurdum (reduction to absurdity), since it ends with a statement that cannot be true.

Examples

A classic proof by contradiction from mathematics is the proof that the square root of 2 is irrational. If it were rational, it could be expressed as a fraction a/b in lowest terms, where a and b are integers, at least one of which is odd. But if a/b = √2, then a² = 2b². Therefore a² must be even. Because the square of an odd number is odd, that in turn implies that a is even. This means that b must be odd because a/b is in lowest terms.

On the other hand, if a is even, then a² is a multiple of 4. If a² is a multiple of 4 and a² = 2b², then 2b² is a multiple of 4, and therefore b² is even, and so is b.

So b is odd and even, a contradiction. Therefore the initial assumption—that √2 can be expressed as a fraction—must be false.

The Length of the hypotenuse is less than the sum of the lengths of the two legs

       The method of proof by contradiction has also been used to show that for any non-degenerate Right triangle, the length of the hypotenuse is less than the sum of the lengths of the two remaining sides. The proof relies on the Pythagorean theorem. Letting c be the length of the hypotenuse and a and b the lengths of the legs, the claim is that a + b > c. As usual, we start the proof by negating the claim and assuming that a + b ≤ c. The next step is to show that this leads to a contradiction. Squaring both sides, we have (a + b)² ≤ c² or, equivalently,a² + 2ab + b² ≤ c². A triangle is non-degenerate if each edge has positive length, so we may assume that a and b are greater than 0. Therefore, a² + b² < a² + 2ab + b² ≤ c². Taking out the middle term, we have a² + b² < c². We know from the Pythagorean theorem thata² + b² = c². We now have a contradiction since strict inequality and equality are mutually exclusive. The latter was a result of the Pythagorean theorem and the former the assumption that a + b ≤ c. The contradiction means that it is impossible for both to be true and we know that the Pythagorean theorem holds. It follows that our assumption that a + b ≤ c must be false and hence a + b > c, proving the claim.

Proof by induction 
       is a very powerful weapon in the number theorist's armory. The idea behind it, though, is a very simple one. Given a conjecture that we wish to prove, we start off by showing that, if it is true for some number n, then it must also be true for the numbern + 1. The second and final stage is to show that the conjecture is true for a given, preferably low, n. If we can do both, then we have effectively shown that the theorem is true for all n greater than or equal to the low value of n for which we proved a specific case. Typically, the second stage involves proving that the conjecture is true for n = 0 or n = 1. (If you prefer, of course, you can do these two steps the other way around. It doesn't matter, as long as you do them both!)
The canonical example of proof by induction is the formula for summation of integers between 1 and n. Before we get going, though, I can't resist relating a (probably true) story on the history of summation.


       Karl Friedrich Gauss (1777 - 1855) was one of the greatest mathematicians who ever lived. He was responsible for a considerable number of mathematical advances. The story is often told of his confounding his mathematics teacher whilst still at a very tender age. Teachers the world over will sympathise when I explain that this particular teacher just wanted a quiet morning. Perhaps he had a lot of marking to do, or perhaps he was still recovering from a cheerful night in the tavern. We don't know. But he can perhaps be forgiven for believing that he could occupy his class for a good part of the morning by asking them to add up all the integers from 1 to 100.


       A proof by induction is just like an ordinary proof in which every step must be justified. However it employs a neat trick which allows you to prove a statement about an arbitrary number n by first proving it is true when n is 1 and then assuming it is true for n=k and showing it is true for n=k+1. The idea is that if you want to show that someone can climb to the nth floor of a fire escape, you need only show that you can climb the ladder up to the fire escape (n=1) and then show that you know how to climb the stairs from any level of the fire escape (n=k) to the next level (n=k+1).

       If you've done proof by induction before you may have been asked to assume the n-1 case and show the n case, or assume the n case and show the n+1 case. This is the same as what I'm explaining here but I will use a different letter because I think it avoids some confusion when trying to figure out what each case is.

Mathematical Notations and Terminology

Set

       is a collection of objects called elements of the set. Why not use the word ``collection'' and eliminate the word ``set'', thereby having fewer words to worry about? ``Collection'' is a common word whose generic meaning is understood by most people. The use of the word ``set'' means that there is also a method to determine whether or not a particular object belongs in the set. We then say that the set is well-defined. For example, it is easy to decide that the number 8 is not in the set consisting of the integers 1 through 5. After all, there are only five objects to consider and it is clear that 8 is not one of them by simply checking all five. 

       A basic problem here is now to indicate sets on paper and verbally. As seen above, a set could be described with a phrase such as ``the integers 1 through 5'' and the speaker hopes that it is understood. Symbollically, we use two common methods to write sets. The roster notation is a complete or implied listing of all the elements of the set. So  A= {a,b,c,d} and B= {2,4,6,8,....,40} are examples of roster notation defining sets with 4 and 20 elements respectively. 

Sequences and Tuples

       A sequence is an ordered list of objects (or events). Like a set, it contains members(also called elements or terms), and the number of terms (possibly infinite) is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence. A sequence is a discretefunction.
       For example, (C, R, Y) is a sequence of letters that differs from (Y, C, R), as the ordering matters. Sequences can be finite, as in this example, or infinite, such as the sequence of all even positive integers (2, 4, 6,...). Finite sequences are sometimes known as strings or words and infinite sequences as streams. The empty sequence ( ) is included in most notions of sequence, but may be excluded depending on the context.
       There are various and quite different notions of sequences in mathematics, some of which (e.g., exact sequence) are not covered by the notations introduced below.
In addition to identifying the elements of a sequence by their position, such as "the 3rd element", elements may be given names for convenient referencing. For example a sequence might be written as (a₁, a₂, a₂, … ), or (b₀, b₁, b₂, … ), or (c₀, c₂, c₄, … ), depending on what is useful in the application.

        A tuple is an ordered list of elements. In set theory, an (ordered) n-tuple is a sequence (or ordered list) of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair. Tuples are usually written by listing the elements within parentheses "( )" and separated by commas; for example, (2,7,4,1,7) denotes a 5-tuple. Sometimes other delimiters are used, such as square brackets "[ ]" or angle brackets "". Braces "{}" are almost never used for tuples, as they are the standard notation for sets.

      Tuples are often used to describe other mathematical objects. In algebra, for example, a ring is commonly defined as a 3-tuple , where E is some set, and " + ", and "" are functions mapping the Cartesian product  to E with specific properties. In computer science, tuples are directly implemented as product types in most functional programming languages. More commonly, they are implemented as record types, where the components are labeled instead of being identified by position alone. This approach is also used inrelational algebra.

Functions and Relations

         A function is one kind of interrelationship among objects. For every finite sequence of objects (called the arguments), a function associates a unique object (called the value). More formally, a function is defined as a set of finite lists of objects, one for each combination of possible arguments. In each list, the initial elements are the arguments, and the final element is the value. For example, the  function contains the list , indicating that integer successor of  is .

       A relation is another kind of interrelationship among objects in the universe of discourse. More formally, a relation is an arbitrary set of finite lists of objects (of possibly varying lengths). Each list is a selection of objects that jointly satisfy the relation. For example, the < relation on numbers contains the list , indicating that  is less than .

       Note that both functions and relations are defined as sets of lists. In fact, every function is a relation. However, not every relation is a function. In a function, there cannot be two lists that disagree on only the last element. This would be tantamount to the function having two values for one combination of arguments. By contrast, in a relation, there can be any number of lists that agree on all but the last element. For example, the list  is a member of the  function, and there is no other list of length 2 with  as its first argument, i.e. there is only one successor for . By contrast, the < relation contains the lists , , and so forth, indicating that is less than , , and so forth.

Graph

       is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study indiscrete mathematics.

       The edges may be directed (asymmetric) or undirected (symmetric). For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this is an undirected graph, because if person A shook hands with person B, then person B also shook hands with person A. On the other hand, if the vertices represent people at a party, and there is an edge from person A to person B when person A knows of person B, then this graph is directed, because knowing of someone is not necessarily asymmetric relation (that is, one person knowing of another person does not necessarily imply the reverse; for example, many fans may know of a celebrity, but the celebrity is unlikely to know of all their fans). This latter type of graph is called a directed graph and the edges are called directed edges or arcs; in contrast, a graph where the edges are not directed is called undirected.

      Vertices are also called nodes or points, and edges are also called lines. Graphs are the basic subject studied by graph theory. The word "graph" was first used in this sense by James Joseph Sylvester in 1878.^[1]

Strings and Languages

Strings

• A string is a finite sequence of symbols from an alphabet written in juxtaposition.

– thecatinthehat

– ablewasiereisawelba

– καoσ

– helloworld!

– 01001000100001

• The string containing no symbols is the empty string, denoted by .

• The set of all strings over alphabet Σ is denoted by Σ∗.

String Operations

• The length of a string is its length as a sequence.

– length of abracadabra is 11

– denoted by absolute values:|abracadabra| = 11

– | | = 0.

Languages

• Let Σ be an alphabet.

• A language over Σ is a set of strings.

• Examples

– Σ∗,

– ∅,

– the palindromes over {0, 1},

– the set of strings over {a, b} that start with a.

• closure If L is a language, then L∗ is the set of all strings formed by concatenating zero or more strings from L.

L∗= ∪∞i=0Li

• positive closure If L is a language, then L+ is the set of all strings formed by concatenating one or more strings from L.

L+ = ∪∞ i=1Li

Boolean logic 

       is the most commonly used logic system nowadays. This is due mostly to the prevalence of computers, which base all of their calculations on Boolean logic. Boolean logic is a binary logic system, meaning that it takes into account two possible states: 0 and 1. These can then be translated into other, more useful meanings. For example, 0 could represent the state "false" and 1 could be "true". Thus one could use Boolean logic to assess the validity of a statement. 0 and 1 can also represent on and off, yes and no, or basically any other pair of opposite states.

Boolean logic is really just a set of rules for the manipulation of given inputs. It consists of a set of "logic gates", each of which is a different set of rules. The three main logic gates are AND, OR, and NOT. AND and OR require two inputs, whereas NOT only requires one. Here is an explanation of each gate:

ANDThe visual representation of the AND gate looks like this:  Sometimes, it is also written like this: Ç (ie. "p AND q" can also be written as "p Ç q") When two inputs are entered into the AND gate, the output is always 0 unless both inputs are 1. Here is a truth table for the AND gate:

p	q	p AND q
1	1	1
1	0	0
0	1	0
0	0	0

ORThe visual representation of the OR gate looks like this:  Sometimes, it is also written like this: È (ie. "p OR q" can also be written "p È q") When two inputs are entered into the OR gate, the output is always 1 unless both inputs are 0. Here is a truth table for the OR gate:

p	q	p OR q
1	1	1
1	0	1
0	1	1
0	0	0

NOTThe visual representation of the NOT gate looks like this:  Sometimes, it is also written like this: - (ie. "NOT p" can also be written as "-p") When an input is entered into the NOT gate, the output is the opposite of that input. In other words, if the input is 1, the output is 0. And if the input is 0, the output is 1. Since both the input and output for a gate are ones and zeros, the output from one gate can serve as the input for another. Two or more gates linked in this fashion are called a logic network. The truth table still functions the same way. For example, consider the network below. P and q are both inputs to the AND gate. Then, the output from the AND gate and q are inputs for the OR gate. The output from the OR gate is input for the NOT gate. The output from the NOT gate is the final result for the whole network.