We have been working very hard since 2009 to facilitate in your learning Read More. We can't keep up without your support. Donate Now.
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 cs402@vu.edu.pk
Tags:
+ 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
bounded automaton.
(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.
E.g.:
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.)
© 2020 Created by +M.Tariq Malik. Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
We are user-generated contents site. All product, videos, pictures & others contents on vustudents.ning.com don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com or Contact us at contact Page with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List | Moderators Group
All Members | Featured Members | Top Reputation Members | Angels Members | Intellectual Members | Criteria for Selection
Become a Team Member | Safety Guidelines for New | Site FAQ & Rules | Safety Matters | Online Safety | Rules For Blog Post