Fichas
Automata
Fichas del conjunto (14)
- 1Finite state machines: * Input is a string * String is processed one symbol at a time, left to right * output is either yes or no * current machine state is the only memory * Output is based on the final stateA finite state automaton is a 5-tuple M = (Q, Σ, δ, q0, F), where:
* Q is a finite set of states
* Σ is a finite alphabet;
* δ : Q × Σ → Q is the transition function;
* q0 ∈ Q is the start state of the machine,
* F ⊆ Q are the accepting or final states.
Eg: ({q0, q1, q2}, {1, 2, C,T}, δ, q0, {q0})
({states}, {alphabet}, {transition}, {initial state}, {final state}) - 2Non-deterministic finite automation: * NFA is just like a DFA but it can have 0 or more state transitions for every symbol * It can have empty transitions * When there is more than one choice of a transition for an input it can follow all possible paths, until one of those paths end up in the final state and then the string is then accepted * They also have bounded memory * for every DFA there exist a NFAA NFA is a 5-tuple M = (Q, Σ, δ, q0, F), where:
* Q is a finite set of states;
* Σ is a finite alphabet;
* δ : Q × Σ → 2^Q is the non-deterministic transition function
* q0 ∈ Q is the start state of the machine
* F ⊆ Q are the accepting or final states. - 3PDA: * PDA is more capable that FA * They have a stack, its operations are : push or pop. Push means to add a symbol to the top of the stack, pop means to remove a symbol from the top of the stack * Stack initially is empty * String is accepted if it reaches the final state and the stack is empty * String is rejected if empty stack is popped, or if stack is not empty in the end, or if the final state is not reached * If an empty stack is popped the PDA halts abnormally Non-determinism in PDAs: * PDA are non-deterministic naturally - Given same input symbol and same top letter in the stack, there can be more than one transitionA PDA is a 6-tuple M = (Q, Σ, Γ, δ, q0, F), where:
* Q is a finite set of states;
* Σ is a finite alphabet;
* Γ is the stack alphabet
* δ : [Q × (Σ ∪ {λ}) × Γ] × [Q × Γ*] is the transition relation
* q0 ∈ Q is the start state of the machine
* F ⊆ Q are the accepting or final states.
Eg: ((q,x,X), (q', a)) ∈ δ:
((current state, input letter, top of stack), (new state, stack replacement)) - 4FSM vs PDA: * in both input is a string which is processed one symbol at a time, left to right * Output is either yes or no * Memory : for FSM its the current state for PDA its the current state and the stack * Both can be non-deterministic * String accepting condition: FSM: final state, PDA: final state and empty stack * FA accept regular languages, PDA accept context free languagesLimitations of FA:
* a FA only has a limited number of states, hence they can only count a finite no. of scenarios
* A FA's memory is only the current state, due to this limited amount of memory we can't build FA for certain languages
EG: we can't build a FA for a string with same amount of a's and b's since it would need to remember how many a symbols it has seen, which is impossible since it has a limited amount of memory
FA can't recognize palindromes, bc to rec. them the machine would need to remember the letter it has seen before (to see if they're then repeated in the reverse order). That means we need an infinite amount of states, hence there's FA can be built for palindromes. - 5Limitations of PDA: * Although PDA has a stack and provides more storage than a FA, it is still a stack so only the last element on it can be accessed * Accessing the earlier elements requires removing the top elements and then you loose them * PDA also must consume input in the order that it is received in, and can't access it again, 'cept by placing it on the stack * Due to these limitations a PDA can't rec certain lanaguages. A PDA only accepts context free languages * Can't recognise {a^nb^nc^n} since its not CF * An eg of CFL is {a^nb^n}, you can push down a token into the stack with every a, and pop a token off for every b * but when you push a token after popping there will be tokens left on the stacks, hence the language would not be acceptedTM NEXT
- 6Turing Machines: * Basically TM = FA + Tape * A TM has an infinite tape where symbols can be written * A head that can read and write on the tape * An instruction table and current state * Unlike PDAs, a TM can access any element in memoryA TM is a 6-tuple (S, Σ, , δ,s0, F), where:
* S is a finite set of states;
* Σ is a finite set of the tape alphabet/symbols;
* ∈ ∈ Σ is the “blank” symbol;
* δ : S × Σ → S × Σ × {L, R} is a partial transition function;
e.g: δ(s, a) = (s',b,R) and δ(s,c) = (s',c,L);
* s0 ∈ S is the initial state;
* F ⊆ S is the set of final or accepting states. - 7* Turing machines are very powerful. They: - infinite memory, finite no. of states, process one symbol at a time, halt if there is not transition defined * They can be used to recognise language, s, which are accepted by the final state, and they can computer functions (produce strings as output) * TM can recognised {a^nb^n | n >= 0}, {a^nb^nc^n | n >= 0}, {a^nb^nc^nd^n | n >= 0}A configuration of a TM T = (S, Σ,∈, δ,s0, F) is a tuple (s,wl, σ, wr), where:
- s ∈ S is the current state of T;
- wl ∈ Σ* is a tape's current string at the left of T's head
- wr ∈ Σ is the tape's current string at the right of T's head
- σ ∈ Σ is the current reading symbol where T’s head is on.
Eg: (sa, ∗aaa∗, b, bb ∗ ccc)
means that the current state is sa, *aaa* is on the left of the machine's head, b is the current symbol being read where the head is on, and bb*ccc is the on the right of T's head - 8TM transistions: δ(s0, 1) = (s1, 0, L) means(current state, whats being read) = move to(new state, write, and move) so we're in state S0 we are reading 1, then we are in state s1, we're writing a 0 and moving LNon-deterministic TM:
- A non-deterministic Turing machine (NTM) may have a set of rules that
gives more than one action for a given situation!
- The transition function now becomes
δ(s, a) = {(s0, a, R),(s2, ∗, L)}
Transition function δ may return a set of possible transitions.
so we are state s and we are reading a, then we can move to state s0 and write a and move right OR we can move to state s2, write * and move left
How do NTMs work?
* A NTM can “guess" any possible legal step at every point.
* A string is accepted if there is a way of always guessing the “correct”
transition - 9Universal turing machine: - A universal TM can simulate an arbitrary Turing machine on arbitrary input. - Given input tape with w and a turing machine M, universal turing machine U outputs U(w,M) = M(w) - Takes TM m as an input (the software) - simulates the actions of M - Hence, takes both instructions data as input
- 10Church-Turing Thesis: - states everything that is computable is computable by a Turing Machine - Its implications are: * We don't need to look for more powerful machines or languages - Enables extreme study of computation - If it can't be done by a TM then it cannot be done at allTM extensions????
- 11Decision Problem: - is a question with a yes-or-no answer, depending on the values of some input parameters Eg: given two no.s x and y, does x evenly divide y? A decision problem is decidable if there exists a Turing Machine to solve it. It's undecidable if no Turing machine exists to solve itHalting Problem: Given a TM M and a string w, does M halt when run on w in the tape?
- Machine will behave in these ways:
* output "yes" if M halts on w
* output "no" if M does not halt on w
ie: keeps looping
The halting problem is undecidable and a TM for it does not exist
Paradox of the halting problem:
1. A Turing Machine that states whether the machine itself halts or not
2. A Turing machine that cannot halt and cannot run forever - 12The result of the Halting Problem means: * It is not the case that there is a TM HALT which: - always halts (for any M and w) - outputs yes if M halts on w - outputs no if M does not halt on w (keeps looping) - produces no other outputs Hence, a machine solving the halting prob must either for some M and w: - not halt - halt and output no, if M halts on w - halt and output yes if M does not halt on w - halt and produce some other output The other machine is the opposite of Halt Hence, option 1 is undesirable, and 2 and 3 are insaneDecision problem reduction: To prove other problems are undecidable
- Problem reduction : decision problem A can be reduced to problem B if we or know how we can solve A if we're given a way to solve B
- The solution to A would somehow "use" the solution for problem B
- But we do not need to know the solution to B
Eg: problem LOOP(M,w) can be reduced to problem HALT(M,w):
- first run HALT(M,w)
-If HALT(M,w) says yes, then LOOP will return no
- If HALT(M,w) says no, then return yes
Problem A reduced to B means:
- If B is decidable, then so is A
- If A is undecidable, then so is B - 13—Halting problem proof
- 14—
