Complexity Theory - Ch1 PDF

Complexity Theory Dr Addisalem Genta  Introduction Complexity : characterizes the behavior of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence. ...

Complexity Theory Dr Addisalem Genta  Introduction Complexity : characterizes the behavior of a system or model whose components interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence.  Automata Theory Automata Theory is an exciting, theoretical branch of computer science. It established its roots during the 20th Century, as mathematicians began developing - both theoretically and literally - machines which imitated certain features of man, completing calculations more quickly and reliably. The word automaton itself, closely related to the word "automation", denotes automatic processes carrying out the production of specific processes. Simply stated, automata theory deals with the logic of computation with respect to simple machines, referred to as automata. Through automata, computer scientists are able to understand how machines compute functions and solve problems and more importantly, what it means for a function to be defined as computable or for a question to be described as decidable.  Automata Theory Automatons are abstract models of machines that perform computations on an input by moving through a series of states or configurations. At each state of the computation, a transition function determines the next configuration on the basis of a finite portion of the present configuration. As a result, once the computation reaches an accepting configuration, it accepts that input. The most general and powerful automata is the Turing machine. The major objective of automata theory is to develop methods by which computer scientists can describe and analyze the dynamic behavior of discrete systems, in which signals are sampled periodically.  Automata Theory The behavior of these discrete systems is determined by the way that the system is constructed from storage and combinational elements. Characteristics of such machines include: Inputs: assumed to be sequences of symbols selected from a finite set I of input signals. Namely, set I is the set {x1, x,2, x3... xk} where k is the number of inputs. Outputs: sequences of symbols selected from a finite set Z. Namely, set Z is the set {y1, y2, y3... ym} where m is the number of outputs. States: finite set Q, whose definition depends on the type of automaton.  Families of automaton There are four major families of automaton : Finite-state machine Pushdown automata Linear-bounded automata Turing machine The families of automata above can be interpreted in a hierarchal form, where the finite-state machine is the simplest automata and the Turing machine is the most complex.  Automata Theory Automata Theory Is the study of abstract computational device (device means which takes input and have an output) Automata = an abstract computing device Automata - are abstract devices and simplified models of real computations Computation happens everywhere: on your laptop, cellphone, etc Why do we need abstract models? Computability – how much the problem can be computable or not? Complexity – how the given problem is complex  Automatons Automatons are abstract models of machines that perform computations on an input by moving through a series of states or configurations. At each state of the computation, a transition function determines the next configuration on the basis of a finite portion of the present configuration. An automaton (Automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).  Language Consider English language It has alphabets = {a, b, c, …, z} Alphabet is any symbol which represent sound Words can be generated by combining alphabets, and combination of words gives us sentences using set of rules. Grammar is the rule to make words or sentences using alphabets ∑ denotes the list of alphabets present in a language For example, In English language ∑ = {a,b,c,…,z}  Alphabets and strings Alphabets is a finite set of symbols Example S1 = {a,b,c,d, …,z} : the set of letters in English S2 = {0,1,2, …, 9} : the set of (base 10) digits S3 = {a,b,c,…,z,#} : the set of letters plus the special symbol # S4 = {(,)} : the set of open and closed brackets Strings A string over alphabet ∑ is a finite sequence of symbols in ∑ The empty string is denoted by ∑ Examples abfbz is a srting over E1= {a,b,c,…,z} 9021 is a tring over E2 = {0,1, …,9} ab#bc is a string over E3 ={a,b,c,…,z,#} ))()(() is a string over E4 = {(,)}  Languages A language is a set of string over an alphabet Languages can be used to describe problems with “yes/no” answers, for example: L1 = The set of all strings over S1 that contain the substring “at” Example L1 = {cat, rat, ate, gate,…} L2 = The set of all strings over S2 that are divisible by 7 Example L2 = {7,14,21,28,…} L3 = The set of all strings of the form s#s where s isany string over S1 Example L3 = {ab#ab, cd#cd, cat#cat, …} L4 = The set of all strings over S4 where every “(“ can be matched with a subsequent “)” Example L4 = {(), (()),(()()), …}  Formal Language Formal language is a language which we define it using mathematical formula. For example, ∑ = {a, b} – a certain language L has only two alphabets L = {set of all the strings of length 2} = {aa, ab, ba, bb} Consider ∑ ={a} ∑2 = ∑ x ∑ = {a}x{a}={aa} ∑3= ∑ x ∑ x ∑ ={a}x{a}x{a}={aaa} ∑0 = means strings of length zero ∑* = ∑0 ꓴ∑1ꓴ ∑2ꓴ ∑3ꓴ ∑4ꓴ … - (Kleene Closure)  Formal Language Consider ∑1 ={x,y} 1. L1={set of all strings of length exactly two} = {w| |w|=2} = {xx, xy, yx, yy} 2. L2 = {set of all strings of length less than or equal to two} = {w| |w| q1, ((q1,0)-> q0)} q0 = {q0} F = {q1}  Finite Automata Example 1: Draw a DFA for the language accepting strings ending with ‘0’ over input alphabets ∑={0, 1} ? And draw the transition table, and find out the 5 tuples Solution: 5 tuple Transition table Q = {qo, q1} 0 1 ∑ = {0,1} δ = {(q0,1)-> q0, (q0,0)-> q1, (q1,0)-> q1, Qo Q1 Q0 (q1,1)-> q0 } q0 = {q0} Q1 Q1 Q0 F = {q1}  Finite Automata Example 2: Draw a DFA for the language accepting strings ending with ‘01’ over input alphabets ∑={0, 1} ? Solution  Finite Automata Example 2: Draw a DFA for the language accepting strings ending with ‘01’ over input alphabets ∑={0, 1} ? Solution Transition diagram 5 tuples Transition table 0 1 Q = {qo, q1, q2} Q0 Q1 Q0 ∑ = {0,1} Q1 Q1 Q2 δ = {(q0,1)-> q0, (q0,0)-> q1, (q1,0)-> q1, Q2 Q1 Q0 (q1,1)-> q2, (q2,0)-> q1, (q2,1)-> q0 } q0 = {q0} F = {q2}  Types of Finite Automata DFA – one input can have only one transition state NFA - one input can have more than one transition state