blog.bazaarvoice.com Umar Faiz Pakistan Institute of Engineering and Applied Sciences LINEAR BOUNDED AUTOMATA • Linear Bounded Automata (LBAs) are the same as Turing Machines with one difference. • A linear bounded automaton (LBA) is a finite state machine with a finite length tape. The tape consists of a sequence of cells, where each cell can store a symbol from the machine’s alphabet. • Symbols can be written or read from any position on this tape. LBA has a read-write head that can be moved left or right one cell. The tape is used both to store the input and any ongoing calculations.
Slides based on Costas Busch - RPI
LINEAR BOUNDED AUTOMATA • There are 2 special symbols, [ and ], that are used to mark the finite bounds of the tape. • The read-write head cannot move beyond either of these symbols and it cannot overwrite these symbols. All computation is done between end markers. Input string [ a b c d e ]
Left-end Working space Right-end
marker in tape marker Slides based on Costas Busch - RPI LINEAR BOUNDED AUTOMATA • A linear bounded automaton (LBA) cannot use extra working space. It can only use the space taken up by the input. The tape alphabet can, in any case, be larger than the input alphabet, which allows the available memory to be increased up to a constant factor.
Slides based on Costas Busch - RPI
LINEAR BOUNDED AUTOMATA The tape is limited in size to the size of the input.
Input string
[ 1 0 1 0 1 ]
Input string
[ 1 0 0 0 0 1 1 0 0 1 0 1 ]
Slides based on Costas Busch - RPI
LINEAR BOUNDED AUTOMATA The tape is limited in size to the size of the input. Input string
[ 1 0 ] tape is limited in size to 2 times the size of the input. Input string
[ 1 0 0 1 ] tape is limited in size to 3 times the size of the input. Slides based on Costas Busch - RPI LINEAR BOUNDED AUTOMATA • At each step the LBA read the symbol under the read-write head, replaces the by another symbol (could be the same symbol) and then perform one of four possible actions – Accept the input string – Reject the input string – Move the read-write head one cell to the left/right
Slides based on Costas Busch - RPI
LINEAR BOUNDED AUTOMATON (LBA) Example languages accepted by LBAs: n n n L {a b c } n! L {a }
• LBA’s have more power than NPDA’s
• LBA’s have also less power than Turing Machines
Slides based on Costas Busch - RPI
LINEAR BOUNDED AUTOMATA A linear bounded automaton can be defined as an 8-tuple (Q, X, ∑, q0, ML, MR, δ, F) where: – Q is a finite set of states – X is the tape alphabet – ∑ is the input alphabet – q0 is the initial state – ML is the left end marker – MR is the right end marker where MR≠ ML – δ is a transition function which maps each pair (state, tape symbol) to (state, tape symbol, Constant ‘c’) – F is the set of final states Slides based on Costas Busch - RPI LINEAR BOUNDED AUTOMATA • If a LBA has q states, g symbols in its tape alphabet, and an input of length n, then the number of its possible configurations is q n gn
Slides based on Costas Busch - RPI
LINEAR BOUNDED AUTOMATA Theorem: • The acceptance problem for linear bounded automata ALBA= {<M, w> | M is an LBA that accepts string w} is decidable.
Slides based on Costas Busch - RPI
LINEAR BOUNDED AUTOMATA Proof: – Simulate M on w. M could accept, reject or loop. – How can we detect looping? – As M computes on w, it goes from configuration to configuration. If M ever repeats a configuration it has already been in, then it must loop forever. LINEAR BOUNDED AUTOMATA • Proof: – An LBA has only qngn distinct configurations where • q is the current state • n is the cell for the current head position • gn is the contents of the tape. n is the number of cells of the tape and each cell can contain one of g possible alphabet symbols. LINEAR BOUNDED AUTOMATA • Proof: – If our input alphabet has 20 symbols, and the tape is limited to thousand cells, then this number would like 20 to one thousand power. It is would be a big number, yet it is finite.
q n gn
Current State Current Cell Contents of the tape
LINEAR BOUNDED AUTOMATA • Proof. – If the machine ever enters a configuration it has ever been in, it must loop forever. To decide ALBA it is enough to simulate M on w for qngn configurations. If the computation of M has not halted in so many steps, it must be in a loop. LINEAR BOUNDED AUTOMATA Theorem: • The empty language problem for linear bounded automata is undecidable.
Slides based on Costas Busch - RPI
Theory of Computation
Chomsky Hierarchy
blog.bazaarvoice.com Umar Faiz Pakistan Institute of Engineering and Applied Sciences THE CHOMSKY HIERARCHY Non Recursively Enumerator) Technical Note: Type-0 Languages Type-1 languages explicitly exclude the null string. (Recursively Enum.) All other language Recursive families permit the null Languages string as a member. (The Venn diagram is in slight error because of this technicality.) Type-1 (Context-sensitive) Languages Type-2 (Context-free) Languages Linear (Context-free) Type-3 Languages (Regular) Languages THE CHOMSKY HIERARCHY According to Noam Chomsky, there are four types of grammars. The following table shows how they differ from each other.
Grammar Grammar Accepted Language Accepted Automaton Type Recursively enumerable Type 0 Unrestricted grammar Turing Machine language Context-sensitive Linear-bounded Type 1 Context-sensitive language grammar automaton
Type 2 Context-free grammar Context-free language Pushdown automaton
Type 3 Regular grammar Regular language Finite state automaton
THE CHOMSKY HIERARCHY Type–3 Grammar: – Type-3 grammars generate regular languages. – These languages generated by these grammars are be recognized by a finite state machines. THE CHOMSKY HIERARCHY Type–3 Grammar: – Type-3 grammars must have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-terminal. – The productions must be in the form X → a or X → aY – where X, Y ∈ N (Non terminal) and a ∈ T (Terminal) – The rule S → is allowed if S does not appear on the right side of any rule. THE CHOMSKY HIERARCHY Type–3 Grammar Example: X→ X→a X → aY THE CHOMSKY HIERARCHY Type–2 Grammar – Type-2 – grammars generate context-free languages. – The productions must be in the form A→γ – where A ∈ N (Non terminal) and γ ∈ (T∪N)* (String of terminals and non-terminals). – These languages generated by these grammars are be recognized by a non-deterministic pushdown automaton. THE CHOMSKY HIERARCHY Type–2 Grammar Example: S→Xa X→a X → aX X → abc X→ THE CHOMSKY HIERARCHY Type–1 Grammar: – Type-1 grammars generate context-sensitive languages. – A Context Sensitive Grammar is a 4-tuple , G = (N,, P, S) where: N=Set of non terminal symbols. =Set of terminal symbols. S=Start symbol of the production. P=Finite set of productions. – The languages generated by these grammars are recognized by a linear bounded automaton. THE CHOMSKY HIERARCHY Type–1 Grammar: – The productions must be in the form αAβ→αγβ • where A ∈ N (Non-terminal) and α, β, γ ∈ (T ∪ N)* (Strings of terminals and non-terminals) – The strings α and β may be empty, but γ must be non-empty. – The rule S → is allowed if S does not appear on the right side of any rule. THE CHOMSKY HIERARCHY Type–1 Grammar Example: AB → AbBc A → bcA B→b THE CHOMSKY HIERARCHY Type–1 Grammar (Context-Sensitive Grammars): n n n is generated by the following context- – The language {a b c } sensitive grammar S abc | aAbc Ab bA Ac Bbcc bB Bb aB aa | aaA THE CHOMSKY HIERARCHY Type–1 Grammar (Context-Sensitive Grammars): – Language {# a # b # c} is generated by following CSG
S ABC CA AC S ABCS CB BC AB BA Aa AC CA Bb BC CB Cc BA AB THE CHOMSKY HIERARCHY Type–1 Grammar (Context-Sensitive Grammars): n n n is generated by the following context- – The language {a b c } sensitive grammar. • The derivation for the string aabbcc is S aSBC S abc | aAbc aaBCBC aabCBC Ab bA aabBCC Ac Bbcc aabbCC bB Bb aabbcC aabbcc aB aa | aaA THE CHOMSKY HIERARCHY Type–1 Grammar (Context-Sensitive Grammars): • Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by CSG but not by context-free grammars.
• Context-sensitive grammars are less general (in the same sense)
than unrestricted grammars. Thus, CSG are positioned between context-free and unrestricted grammars in the Chomsky hierarchy. THE CHOMSKY HIERARCHY Type–0 Grammar: • Type-0 grammars generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars. • They generate the languages that are recognized by a Turing machine. • The productions can be in the form of α → β where α is a string of terminals and non-terminals with at least one non-terminal and α cannot be null. β is a string of terminals and non-terminals. THE CHOMSKY HIERARCHY • Type–0 Grammar Example: S → ACaB Bc → acB CB → DB aD → Db GRAMMARS LANGUAGES & ACCEPTING MACHINES Grammars Languages Accepting Machines Type 3 grammars: Regular DFA Regular grammars, languages NDFA Left-linear grammars, Right-linear grammars Type 2 grammars: Context-free PDA Context-free grammars languages Type 1 grammars: Contest-sensitive Linear-bounded Context-sensitive grammars, languages Automata Monotonic grammars Type 0 grammars: Recursively DTM Phrase-structure grammars, enumerable, NDTM Unrestricted grammars Unrestricted
