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.

www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

# Graded Discussion Board (GDB) CS402 will be conducted on August 10, 2015

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

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

Views: 3613

Attachments:

### Replies to This Discussion

Aslam o alikum

yar koi bta skta ha k GDB konse lecture me cover hogi .....

TM from lecture 45 gdb ka mtlab hai k 10 august tak ap ko 45 lectur complete hony chahye uff

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.

es diagram mein state 2 ki dono transition b b hain same for state 4 ye kia hai FA mein tu hr state sy a, aur b jati hain any one plz exaplain

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.)

## Latest Activity

+M.Tariq Malik liked Fatima's discussion mgt503
3 hours ago
+M.Tariq Malik liked Fatima's discussion MGT503 short notes
3 hours ago
MUHAMMAD IHSAN ULLAH and maria shams are now friends
3 hours ago
Fatima posted discussions
3 hours ago
4 hours ago
+M.Tariq Malik posted discussions
4 hours ago
4 hours ago
нαρρү cнαη∂α] •._.•´¯)'s discussion was featured

4 hours ago

1

2