Finite Machines

  • Finite Automaton Definition:

    • A finite automaton is a 5-tuple (Q, , δ, q0, F), where:

      • Q is a finite set called states
      • is a finite set called alphabet
      • δ: Q × Q is the transition function
      • q0 Q is the start state
      • F Q is the set of accept states (final sates)
  • Explaining the definition:

    • The definition is called 5-tuple because it consists of 5 parts
    • We use something called a transition function denoted by δ to define rules for moving. If a finite automaton has an arrow from state x to state y labeled with the input symbol 1, that means if the automaton is in state x and it reads 1 it moves to y this transition is denoted as δ(x, 1) = y. This notation is a kind of mathematical shorthand
    • δ: Q × Q. This means that the domain of δ function is combined from Q × and the range is Q (From the functions properties, Introduction)
  • If the start state is also an accept state therefore M accept
  • A language is called regular language if some finite automaton recognizes it
  • Steps for how to think as a machine:

  • You have to figure out what you need to remember about the string you are reading it (we call it crucial information)
  • List the possibilities that the crucial information depend on
  • Assign the transitions, how to go from one possibility to another
  • Set the start state, that means the state of possibility seeing 0 symbols
  • Set the accept states
  • Nondeterministic is a generalization of deterministic

Regular Languages

  • The theory of computation begins with a question: What is a computer?
  • We use computational model to set up a manageable mathematical theory of computer
  • Any computational model may be accurate is some situations and not in others
  • Finite State Machine (Finite Automaton):

    • This model is designed for computers with limited amount of memory
    • Examples:

      • Automatic Door Controller

        • The controller contains just a single bit of memory, capable of recording which of the two states (Open, Closed) the controller is in
      • Elevator Controller
      • Dishwashers
      • Electronic Thermostats
      • Part of digital watches
      • Calculators
    • Finite automata and their probabilistic counterpart Markov chains are useful tools when we are attempting to recognize pattern in data. These devices are used in speech processing and in optical character recognition. Markov chains have even been used to model and predict price changes in financial markets
    • Now we will develop:

      • Precise definition of finite automata
      • Terminology for describing and manipulating finite automata
      • Theoretical results that describe power and limitations of finite automata
    • General mathematical theory of finite automata called M1

      Figure 1.0

    • Figure 1.0 is called the state diagram if M1. It has three states labeled q1, q2 and q3. The start state q1 is indicated by the arrow pointing at it from nowhere. Accept state q2 is the node with double circle. The arrows going from one state to another is called transitions
    • Working Mechanism:

      • The finite automaton accept input string (such as 1101)
      • The automaton receives the symbols from the input string one by one (1 then 1 then 0 then 1)
      • After reading each symbol M1 moves from one state to another
      • When it reads the last symbol M1 produce the output
      • The output is considered as accept if M1 now in an accept state and reject if it is not
      • M1 language:

        • After various examining we conclude that M1 accepts any string that

          • Ends with a 1(1, 11, 0011 or 010101)
          • Ends with an even number of 0s following the last 1 (100 or 0100)
      • Formal Definition of A Finite Automaton:

        • Defining Rules:

          • A formal definition is precise and resolves any uncertainties about what is allowed in a finite automaton
          • Formal definition provides notations. Good notation helps you think and express your thoughts clearly
          • Mention the references
        • Finite Automaton Definition:

          • A finite automaton is a 5-tuple (Q, , δ, q0, F), where:

            • Q is a finite set called states
            • is a finite set called alphabet
            • δ: Q × Q is the transition function
            • q0 Q is the start state
            • F Q is the set of accept states (final sates)
          • Explaining the definition:

            • The definition is called 5-tuple because it consists of 5 parts
            • We use something called a transition function denoted by δ to define rules for moving. If a finite automaton has an arrow from state x to state y labeled with the input symbol 1, that means if the automaton is in state x and it reads 1 it moves to y this transition is denoted as δ(x, 1) = y. This notation is a kind of mathematical shorthand
            • δ: Q × Q. This means that the domain of δ function is combined from Q × and the range is Q (From the functions properties, Introduction)
        • Now, we will apply M1 on the finite automaton formal definition:

          • M1 = (Q, , δ, q0, F), where:

            • Q = {q1, q2, q3}
            • = {0, 1}
            • δ is described as:

              0

              1

              q1

              q1

              q2

              q2

              q3

              q2

              q3

              q2

              q2

            • q1 is the start state
            • F = {q2}
      • If A is the set of all strings that machine M accepts, we say that A is the language of machine M and write L(M) = A. We say that M recognize A or that M accepts A. If the machine accepts no strings it still recognizes one language namely the empty language

        • In our example let A = {w | w contains at least one 1 or an even number of 0s follow the last 1}
        • Then, L(M1) = A or equivalently M1 recognizes A
      • A good way to begin understanding any machine is to try it on some sample input strings
      • If the start state is also an accept state therefore M accept
    • Formal Definition of Computation:

      • Defining the computation of finite automata (Informally)

        • Let M = (Q, , δ, q0, F) be a finite automaton and let w = w1 w2wn be a string where each wi is a member of the alphabet . Then M accepts w if a sequence of set r0, r1,…rn in Q exists with three conditions:

          • r0 = q0
          • δ(ri, wi+1) = ri+1, for i = 0, …, n – 1
          • rn F
        • Condition 1 says that the machine stars in the start state. Condition 2 says that the machine goes from state to state according to the transition function. Condition 3 says that the machine accepts its input if it ends up in the accept state. We say that M recognizes languages A if A = {w | M accept w}
        • A language is called regular language if some finite automaton recognizes it
    • Designing Finite Automata:

      • To design automata, put yourself in the place of the machine you are trying to design and then see how you would go about performing the machine’s task
      • Steps for how to think as a machine:

        • You have to figure out what you need to remember about the string you are reading it (we call it crucial information)
        • List the possibilities that the crucial information depend on
        • Assign the transitions, how to go from one possibility to another
        • Set the start state, that means the state of possibility seeing 0 symbols
        • Set the accept states
    • The Regular operations:

      • Now we will investigate the finite automata and regular languages properties
      • In arithmetic, the basic objects are numbers and the tools are operations for manipulating them, such as + and ×. In the theory of computation the objects are languages and the tools include operations specifically designed for manipulating them. We will define three operations on languages called regular operations and we will use them to study properties of the regular languages
      • Let A and B be languages, we define the regular operations union, concatenation, and star as follows:

        • Union: A B =
        • Concatenation: A B =
        • Star(Cloture):
      • The star operation is a unary operation; it works by attaching any number of strings in A together to get a string in the new language. Because "any number" includes 0 as a possibility, the empty string is always a member of , no matter what A is
      • A collected of objects is closed under some operations if applying that operation to members of the collection returns an object still in the collection
      • Theorem 1.0:

        • The class of regular languages is closed under the union operation
      • Theorem 2.0:

        • The class of regular languages is closed under the concatenation operation
    • Nondeterminism:

      • Deterministic computation means that when we know the machine’s next state
      • Nondeterministic means that several choices may exist for the next state. Nondeterministic is a generalization of deterministic
      • We can convert a NFA to DFA with more stats
    • Formal Definition of Nondeterministic Finite Automaton:

      • The DFA differs from NFA in the transition function
      • A nondeterministic finite automaton is a 5-tuple, where

        • Q is a finite set called states
        • is a finite set called alphabet
        • δ: Q × P(Q) is the transition function
        • q0 Q is the start state
        • F Q is the set of accept states (final sates)
      • Where
      • And P(Q) is called the power set of Q, where P(Q) is the collection of all subsets of Q
    • Equivalence of NFD and DFA:

      • Two machines are equivalence if they can recognize the same language
      • Theorem 3.0:

        • Every NFA has an equivalence DFA
    • Converting NFA to DFA:

      • Determines the DFA states: it’s the power set of the NFA
      • Determine start and accept states of DFA
  • Regular Expressions:

    • Regular Expression:

      • Using regular operations to describe language
    • Regular expressions are fields:

      • used in text patterns searching
      • In the design of compilers of programming languages
    • In regular expressions the star operation is done first, followed by concatenation and finally union
    • Formal Definition of Regular Expression:

      • Say that R is a regular expression if R is:

        • for some a in ∑
        • Ø
        • , where and are regular expressions
        • , where and are regular expressions
        • , where and is regular expressions
    • We are in danger of defining the notion of regular expression in terms of itself. If true, we would have a circular definition which would be invalid. Thus, we actually are defining regular expressions in terms of smaller regular expressions, this is called inductive definition
    • Elemental objects in programming languages are called tokens, such a variable names and constants may be described with regular expressions. A numerical constants that my include factorial part and/or a sign may be described as the regular expression: (+ – )(D+ D+.D* D*.D+)

      • Where D = {0, 1, 2, 3, ,4 , 5, 6, 7, 8, 9}
    • Once the syntax of the tokens of the programming language have been described, automatic systems can generate the lexical analyzer, the part of a compiler that initially process input program
    • Equivalence with Finite Automata:

      • Theorem:

        • A language is regular if and only if some regular expression describes it
    • Converting Regular Expressions to FA:

      • See the examples with this file
    • Converting FA to Regular Expression:

      • There are two parts:

        • First, we convert the DFA to generalized nondeterministic finite automaton (GNFA)
        • Then converting the GNFA to regular expression
      • GNFA:

        • Are usual NFA where the transition arrows may have any regular expression as labels instead one member
        • It can read a block of symbols at one time
        • GNFA should meets the following conditions:

          • The start state has out coming arrows to every other state and there is no incoming arrows
          • There is only one accept state, and it has arrows coming in from every other state but no arrows are going out
          • Except for the start and accept states, one arrow goes from every state to every other state including the state itself
        • Converting from DFA to GNFA is simply by:

          • Adding new start state with arrow to the old start state
          • Adding new accept state with arrows to the old accept states
          • I any arrows have multiple labels, we replace each with a single arrow whose label is the union of the previous labels

            • Or if we have three or multiple arrows going between the same two states in the same direction
          • Finally, adding arrows labeled between states that had no arrows

            • A transition labeled with can never be used
          • Converting GNFA into regular expression:

            • Say that GNFA has k states

              • k ≥ 2
              • if k > 2 we construct an equivalence GNFA with k – 1 states
              • Repeat the previous state till we have k = 2

                • Where the GNFA has a single arrow that goes from the start state to the accept state
                • The label of this arrow is the equivalence regular expression
        • Example: the stages in converting a DFA with three states to an equivalence regular expression are shown in the following figure:
        • Figure 1.62
      • A generalized nondeterministic finite automation us a 5tuple (Q, ∑, , qstart, qaccept), where:

        • Q is a finite set of states
        • ∑ is the input alphabet
        • , is the transition function
        • is the accept state
        • is the start state
      • The procedure CONVERT(G) takes a GNFA and converts it to an equivalence regular expression
      • CONVERT(G):

        • Let k be the number of states of G
        • If k = 2, then G must consist of a start state, an accept state and a single arrow connecting them labeled with regular expression R.
          Return the expression R
        • If k > 2, we select any state Q different from and and let G’ be the GNFA (Q’, ∑, , qstart, qaccept), where

          • Q’ = Q – {}
          • And for any Q’ – {} and      Q’ – {} let
            for , , ,
        • Complete CONVERT(G’) and return its value
  • Non Regular Languages:

    • Here we will prove that there are some languages that are not recognized by FA
    • Example: , this languages couldn’t be recognized by any FA
    • The Pumping Lemma for regular languages:

      • We will prove the non-regularity by the pumping lemma that states all regular languages have special property so, if we can show that a languages doesn’t have this property we are guaranteed that its non-regular language

The property states that all strings in a language can be "pumped" if they are at least as long as a certain special value called pumping length. That means each string contains a section that can be replaced by any number of times with the resulting string remaining in language

Introduction to Theory of Computation

  • Aim of the course:

    • Determine what can and can’t be computed
    • How quickly
    • With how memory
    • On which type of computational model
  • First problem:

    • Given a number contains of 500 digits can you find its factors in a reasonable amount of time?
    • Answer: no one presently knows how to do that in all cases within the life time of the universe!
  • Theory of Computation Central Areas:

    • Automata
    • Computability
    • Complexity
  • The three areas are linked together by the question

    • What are the fundamental capabilities and limitations of computers?
  • History:

    • This question goes back to 1930s when mathematical logicians first began to explore the meaning of computation.
  • Complexity Theory:

    • Computer problems either hard or easy. Easy problems like sorting number even microcomputers can sort million of numbers. Now, consider a scheduling problem for entire university under some constrains (no two classes share the same room at the same time, the instructors limitations…etc), finding the best schedule may require centuries, even with a supercomputers
    • So we have a new question that says:

      • What makes some problems computationally hard and others easy?
    • This is the central question of the complexity theory!
    • Researches have discovered and elegant scheme for classifying problems according to their computational difficulty. It’s analogous ( تشبه ) to the periodic table for classifying elements according to their chemical properties
    • The Classification Rules, any problem is classified as computationally hard problem according to the following:

      • If you can alter the root difficulty of the problem so that it becomes more solvable
      • You can settle for less than a perfect solution ( hardness of getting a perfect solution )
      • Some problems are hard only in the worst case but in other cases are easy. This alternation of difficulty comes from the application that is solving this problem
      • If there isn’t exist alternative types of computation (such as randomization) that can speed up some tasks
    • One applied area has been affected directly by complexity theory is the field of cryptography (علم التشفير)
    • The key of this relation is that in the other fields they want easy problems to solve but in cryptography we want hard problems instead of easy problems (because secret codes should be hard to break)
  • Computability Theory:

    • During the first half of the 20s century, mathematics such as Kurt, Alan Turing, Alonzo Church has discovered that certain basic problems couldn’t be solved by the computers. One of these problems is the problem of determining whether a mathematical statement is either true or false!!!
    • The previous problem lead to develop the theoretical models of computers that can solve this problems
    • There are similarity between complexity and computability that complexity classify according to hard and easy where computability classify according to solvable or not solvable by computers
  • Automata Theory:

    • Automata theory deals with the definitions and properties of mathematical models of computation
    • Examples of these models:

      • Finite Automaton: used in text processing, compilers and hardware design
      • Context-Free-Grammar: used in programming languages and AI
    • The theories of computability and complexity require a precise definition of computer, and this is the role of automata
  • Mathematical Notations and Terminology:

    • Here we will describe basic mathematical objects, tools and notations that we will use
    • Sets (Studied Before ):

      • A set is a group of objects represented as a unit
      • The objects of the set are called members or elements
      • Ways of defining sets:

        • By listing the elements of the set inside braces{}:

          • {7, 21, 57}
        • By rules:

          • Set A = {n | rule about n}, Example :

            • {n | n = m2 for m }
      • Sets notations:

        • , ,
      • Sets types: Multiset, infinite set, empty set,
      • Venn diagram
    • Sequence and Tuples (Studied Before ):

      • A sequence of objects is a list of these objects in the same order
      • Sequences are listed within parentheses ()
      • Here we care about the order of elements in the sequence
      • Finite sequences are called tuples
      • Sequence with k elements is called k-tuple

        • 2-tuple is called pair
      • Cartesian product
    • Functions and Relations (Studied Before ):

      • A functions is an object that sets up an input-output relation
      • Function are also called mapping
      • Domain: the set of possible inputs for a function
      • Range: the set of possible outputs for a function
      • The input for a function is called arguments to f
      • A function with k arguments is called k-ary functions and k is called arity of the function
      • If k = 1 then the function is called unary function
      • If k = 2 then the function is called binary function
      • Infix notation: like we say f = x + y
      • Prefix notation: like we say f = add(x, y)
      • A predicate or property is a function whose range is {True, False}
      • When a property has domain of k-tuples it’s called relation
      • The notation for saying that is a function with domain D and range R is:

      • Ways of describing functions:

        • Table
        • When we do modular arithmetic (say by n) on inputs in a function then we define the function with the notation:
      • A special type of binary relation called equivalence relation that means two objects are equal in some features
      • A binary relation R is an equivalence relation if it satisfies the conditions:

        • Reflexive
        • Symmetric
        • Transitive
    • Graphs:

      • An undirected graph or simply graph is a set of points with lines connecting some of the points.
      • The points are called nodes or vertices and the lines are called edges
      • The number of edges at particular node is the degree of the node
      • No more than one edge is allowed between any two nodes
      • If V is the set of nodes of G and E is the set of edges then we say G = (V, E)
      • Graphs are used to represented data
      • We say that graph G is a subgraph of graph H if nodes of G are a subset of the nodes of H and the edges of G are a subset of the edges of H
      • A path in a graph is a sequence of nodes connected by edges
      • A simple path is a path that doesn’t repeat any nodes
      • A graph is connected if every two nodes have a path between them
      • A path is cycle if it starts and ends in the same node
      • A simple cycle is the cycle that contains at least 3 nodes and repeats only the first and last node
      • A graph is a tree if it’s connected and has no simple cycles
      • The nodes of degree 1 other than the root are called leaves
      • If the graph has arrows instead of lines it’s called directed graph
      • The number of arrows pointing from a particular node is the outdegree
      • The number of arrows pointing to a particular node is the indegree
      • A path in which all the arrows point in the same direction as its steps is called a directed path
      • A directed graph is strongly connected if a directed path connects every two nodes
    • String and Languages:

      • Alphabet is any nonempty finite set
      • The members of alphabet are called symbols
      • We generally use letters to designate alphabets and typewriter front for symbols from an alphabet
      • A string over an alphabet is a finite sequence of symbols from that alphabet
      • If w is a string over , the length of w (written as |w|) is the number of symbols it contains
      • The string of length zero is called empty string written as
      • The empty string plays the role of 0 in a number system
      • If w has length n we can write w = w1 w2 wn where each wi
      • The reverse of w, written as wR is the string obtained by writing the opposite order
      • String z is substring of w if z appears consecutively within w
      • If we have string x of length m and string y of length n, the concatenation of x and w written xy is the string obtained by appending y to the end of x
      • The lexicographic ordering of strings is the same as the familiar dictionary ordering, expect that shorter strings precede longer strings

        • Thus, the lexicographic ordering of all strings over the alphabet {0, 1} is: ( , 0, 1, 00, 01, 10, 11, 000, …. )
      • A language is a set of strings
    • Boolean Logic:

      • Boolean logic is a mathematical system built around the two values True and False
      • The values True and False are called Boolean values
      • Boolean Operations:

        • NOT, negation, ¬
        • AND, conjunction,
        • OR, disjunction,
        • XOR, exclusive or,
        • XNOR, exclusive nor,
        • Equality, ↔
        • Implication, →
      • We use Boolean operations for combining simple statements into more complex Boolean expression
      • Operands of operation
      • Distributive low for AND and OR are similar to + and ×
  • Definitions, Theorems and Proofs:

    • Theorems and proofs are soul and heart of math and definitions are its spirit
    • Definitions describe the objects and notations we use
    • The definitions may be easy as the definition of set or complex as the definition of security in a cryptography system
    • After we have defined various objects and notations we usually make mathematical statements about them, these statements express that some object has a certain property
    • Proof is a convincing logical argument that a statement is true
    • Theorem is a mathematical statement proved true
    • Lemmas Statements are statements that are used to proof other statements
    • The theorem or its proof may allow us to conclude easily that other related statements are true these statements are called corollaries
    • Finding Proofs:

      • Steps to find proof:

        • Carefully read the statement you want to proof
        • Understand all notations
        • Rewrite the statement in your own words
        • Break it down and consider each part separately
      • Multipart Statements:

        • P Q: if P is true then Q is true (iff), forward direction
        • P Q: if Q is true then P is true (if), reverse direction
        • PQ: P is true if Q is and Q is true if P is
        • A = B: every member of A is also a members of B
      • If statement says that all objects of a certain type have a particular property, pick a few objects of that type and observe that they actually do have that property. After that try to find object that fails to have the property called a counterexample. If the statement is true then, you won’t find the counterexample object
      • If you are stuck to prove a statement, try something easier. Attempt to prove special cases of statement till you can extract a general case of this statement
      • Writing proofs:

        • A well-written proof is a sequence of statements wherein each one follows by simple reasoning from the previous statement in the sequence
      • Proofs Producing Tips:

        • Be patient
        • Come back to it:

          • read the statement then leave it and come back after hours
        • Be neat:

          • User simple clear pictures and text
        • Be concise:

          • Brevity helps you express high-level ideas without getting lost in details. Good mathematical notation us useful for expressing ideas concisely
  • Types of Proofs:

    • Proof By Construction:

      • When to user:

        • Many theorems state that a particular type of object exists. One way to prove such a theorem is by demonstrating how to construct the object
      • Proof By Contradiction:

        • Here we assume that the theorem is false and then show that this assumption leads to an obviously false consequence
        • Rational number: A number is rational if it’s a fraction m/n where m and n are integers
      • Proof By induction:

        • Proof by induction is an advanced method used to show that all elements of an infinite set have a particular property
  • Construction of Induction Proof:

  • Induction Step:

    • This step proofs that for each i ≥ 1, so we first
    • Assume that P(i) is true then, (Induction Hypothesis)
    • Proof that P(i+1) is also true (Induction Step)
  • Basis Step: This step proof that P(1) is true (simplest number)