GDP diagramFor the given Finite Automaton click here Both Linear Bound Automata (LBA) and Turing machine (TM) can be used to express the language accepted by above Finite Automaton (FA). Which of LBA or TM would you choose to express the given language and why? Justify your decision with logical reasons. Try to provide precise and to the point comments avoiding irrelevant details. For any query, feel free to email at email@example.com
+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)
+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)+ Click Here to Search (Looking For something at vustudents.ning.com?) + Click Here To Join (Our facebook study Group)
Aslam o alikum
yar koi bta skta ha k GDB konse lecture me cover hogi .....
Both Linear Bound Automata (LBA) and Turing machine (TM) can be used to express the language accepted by above Finite Automaton (FA). Which of LBA or TM would you choose to express the given language and why? Justify your decision with logical reasons.
koi ALLAH ka bnda discus kry plzzzzzzzzzzzzzz
yahn sub hi Allah key bandy hi hain lakin ati kisi ko nahi na
Definition. A linear bounded automaton (lba) is a multi-track Turing
machine which has only one tape, and this tape is exactly the same length
as the input.
(By the way, we could intuitively indicate why lba's are more powerful than pushdown machines. Two observations are necessary. First, a tape which can be read and written upon is as powerful a tool as a stack. Then, note that a pushdown machine can only place a bounded number of symbols on its stack during each step of its computation. Thus its stack cannot grow longer than a constant times the length of its input.) The other relationship we need is not available. Nobody knows if nondeterministic linear bounded automata are more powerful than ordinary ones.
A Turing machine that uses only the tape space occupied by the input is
called a linear-bounded automaton (LBA).
An equivalent definition of an LBA is that it uses only k times the
amount of space occupied by the input string, where k is a constant
fixed for the particular machine.
A Turing machine consists of a finite-state control unit, equipped
with a memory tape, infinite in both directions. Each cell on the
tape contains a symbol drawn from a finite alphabet Γ.
The machine therefore has just a finite amount of memory,
determined by the length of the input string. We call this a linear
(LBAs are sometimes defined as having tape length bounded by a
constant multiple of length of input string — doesn’t make any
difference in principle.)
Theorem: A language L ⊆ Σ∗ is context-sensitive if and only if
L = L(T) for some non-deterministic linear bounded automaton T.
Rough idea: we can guess at a derivation for s. We can check each
step since each sentential form fits within the tape.
Turing machines are important because (it’s generally believed
that) anything that can be done by any mechanical procedure or
algorithm can in principle be done by a Turing machine. This is
called the Church-Turing Thesis.
Any language L ⊆ Σ∗ that can be ‘recognized’ by some
mechanical procedure can be recognized by a TM.
Any mathematical function f : N → N that can be computed
by a mechanical procedure can be computed by a TM (e.g.
representing integers in binary, and requiring the TM to write
the result onto the tape.)