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

Looking For Something at vustudents.ning.com? Click Here to Search

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

How to Add New Discussion in Study Group ? Step By Step Guide Click Here.

CS402 - Theory of Automata Graded Discussion Board(GDB) will be conducted on February 23, 2015.

Dear students,

The activity of Graded Discussion Board (GDB) will be conducted on February 23, 2015

Students will be able to post their comments for 48 hours only.

GDB Topic:

Can Push Down Automaton (PDA) with n-stacks be equally powerful to a Turing machine while dealing Context Free Languages (CFG)?

Justify your point of view with logical reasons in either case.

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 Follow the New Added Discussions at Your Mail Address?

+ 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?


See Your Saved Posts Timeline

Views: 3869

.

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

Replies to This Discussion

Dant dekhany sy kam nahi chaly ga GDB ka solution post karo

Is there anyone can explain me on my skype ID smsalmanr

I am out of Pakistan, would be appreciated. Thanks

I'm unable to understand the concepts of PDA so far....

can anyone explain the gdb...........

Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines. Deterministic pushdown automata can recognize alldeterministic context-free languages while nondeterministic ones can recognize all context-free languages. Mainly the former are used in parser design.

PUSHDOWN AUTOMATON (PDA)[ including the possibility of non determinism]
Pushdown Automaton (PDA), consists of the following
1. An alphabet Σ of input letters.
2. An input TAPE with infinite many locations in one direction. Initially the input string is placed in it
starting from first cell, the remaining part of the TAPE is empty.
3. An alphabet Γ of STACK characters.
4. A pushdown STACK which is initially empty, with infinite many locations in one direction. Initially
the STACK contains blanks.
5. One START state with only one out-edge and no in-edge.
6. Two halt states i.e. ACCEPT and REJECT states, with in-edges and no out-edges.
7. A PUSH state that introduces characters onto the top of the STACK.
8. A POP state that reads the top character of the STACK, (may contain more than one out-edges with
same label).
9. A READ state that reads the next unused letter from the TAPE, (may contain more than one out-edges
with same label).

Turing machine
The mathematical models (FAs, TGs, PDAs) that have been discussed so far can decide whether a string is
accepted or not by them i.e. these models are language identifiers. However, there are still some languages
which can’t be accepted by them e.g. there does not exist any FA or TG or PDA accepting any non-CFLs.
Alan Mathison Turing developed the machines called Turing machines, which accept some non-CFLs as well,
in addition to CFLs.
Definition
A Turing machine (TM) consists of the following
An alphabet Σ of input letters.
An input TAPE partitioned into cells, having infinite many locations in one direction. The input string is placed
on the TAPE starting its first letter on the cell i, the rest of the TAPE is initially filled with blanks (’s).

A tape Head can read the contents of cell on the TAPE in one step. It can replace the character at any cell and
can reposition itself to the next cell to the right or to the left of that it has just read. Initially the TAPE Head is at
the cell i. The TAPE Head can’t move to the left of cell i. the location of the TAPE Head is denoted by .
An alphabet Γ of characters that can be printed on the TAPE by the TAPE Head. Γ may include the letters of Σ.
Even the TAPE Head can print blank , which means to erase some character from the TAPE.
Finite set of states containing exactly one START state and some (may be none) HALT states that cause
execution to terminate when the HALT states are entered.
A program which is the set of rules, which show that which state is to be entered when a letter is read form the
TAPE and what character is to be printed. This program is shown by the states connected by directed edges
labeled by triplet (letter, letter, direction). It may be noted that the first letter is the character the TAPE Head
reads from the cell to which it is pointing. The second letter is what the TAPE Head prints the cell before it
leaves. The direction tells the TAPE Head whether to move one cell to the right, R, or one cell to the left, L.

Note
It may be noted that there may not be any outgoing edge at certain state for certain letter to be read from the
TAPE, which creates nondeterminism in Turing machines. It may also be noted that at certain state, there can’t
be more than one out going edges for certain letter to be read from the TAPE. The machine crashes if there is
not path for a letter to be read from the TAPE and the corresponding string is supposed to be rejected.
To terminate execution of certain input string successfully, a HALT state must be entered and the corresponding
string is supposed to be accepted by the TM. The machine also crashes when the TAPE Head is instructed to
move one cell to the left of cell i.

TURING MACHINE

 

PUSHDOWN AUTOMATON (PDA)[ INCLUDING THE POSSIBILITY OF NON DETERMINISM]


An alphabet  of input letters

 

1. An alphabet  of input letters.

An input TAPE partitioned into cells, having infinite many locations in one direction. The input string is placed

on the TAPE starting its first letter on the cell i, the rest of the TAPE is initially filled with blanks (_’s).

 

An input TAPE with infinite many locations in one direction. Initially the input string is placed in it starting from first cell, the remaining part of the TAPE is empty

A tape Head can read the contents of cell on the TAPE in one step. It can replace the character at any cell and

can reposition itself to the next cell to the right or to the left of that it has just read

 

An alphabet Γ of STACK characters.

Initially the TAPE Head is at

the cell i. The TAPE Head can’t move to the left of cell i. the location of the TAPE Head is denoted by .

A pushdown STACK which is initially empty, with infinite many locations in one direction. Initially
the STACK contains blanks.

An alphabet Γ of characters that can be printed on the TAPE by the TAPE Head. Γ may include the letters of Σ.

Even the TAPE Head can print blank _, which means to erase some character from the TAPE.

 

 

One START state with only one out-edge and no in-edge.

Finite set of states containing exactly one START state and some (may be none) HALT states that cause

execution to terminate when the HALT states are entered.

 

Two halt states i.e. ACCEPT and REJECT states, with in-edges and no out-edges.

 

A PUSH state that introduces characters onto the top of the STACK.

 

A POP state that reads the top character of the STACK, (may contain more than one out-edges with
same label).

 

A READ state that reads the next unused letter from the TAPE, (may contain more than one out-edges
with same label).

 

please help to find the GDB best answer. I have studied these topics again again. But i am not able to find exact answer. I think the table i have uploaded the answer lies in it only the expert in the subject of theory of automata can tell us one clue to solution. so please any body have any idea please share. 

Please visit this page for Review:

http://ceur-ws.org/Vol-788/paper3.pdf

Firstly, the class of languages recognised by Turing Machines is not context sensitive, it's recursively enumerable (context sensitive is the class of languages you get from linear bound automata).

RSS

Today Top Members 

1 Biya

Biya

2 Asad

Asad

3 Ahmad

Ahmad

© 2019   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service

.