We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

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

Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

# 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

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?

Views: 3569

.

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

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

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

2 minutes ago
Waseem Khan posted a discussion

### E-Music SRS

4 minutes ago
+ M.Tariq Malik's 12 discussions were featured
4 minutes ago
+ M.Tariq Malik added a discussion to the group BIO102 Basic II-Chemistry

### BIO102 Current Mid Term Papers Fall 2019 (14 to 26 December 2019) & All Solved Past Papers, Solved MCQs & Helping Material

5 minutes ago
+ M.Tariq Malik added a discussion to the group BIO101 Basic I-Biology

### BIO101 Current Mid Term Papers Fall 2019 (14 to 26 December 2019) & All Solved Past Papers, Solved MCQs & Helping Material

14 minutes ago
16 minutes ago
"mth404 2nd assignment sol plz????????????/"
20 minutes ago

1

2

3