 |
CS402 GDB NO. 1 FALL 2022 |
CS402 GDB NO. 1 FALL 2022 || 100% RIGHT SOLUTION || THEORY OF AUTOMATA || BY VuTech
GDB QUESTION
A group of computer
scientists at Manchester University, UK needs a machine to implement a language
L={yy1 where y1 = Rev(y), yE (0,1)*} i.e, L = {00, 11,
0110, 001100, 010010,…….}
The machine should
fulfill the following points:
·
Each input alphabet can have more than one
possibility to move to the next state.
·
No space limitation.
Now, which of the
following machine(s) will be the most favorable in order to achieve the above
characteristics?
·
Finite Automation with Stack
·
Non-Deterministic Push Down Automata
·
Push Down Automata with 2 Stacks
Justify your answer with
valid reasons.
SUBSCRIBE, SHARE, LIKE AND COMMENTS FOR MORE UPDATES
KINDLY, DON’T COPY PASTE
SEND WHATSAPP OR E-MAIL FOR ANY QUERY
0325-6644800
kamranhameedvu@gmail.com
Solution:
I will choose
Non-Deterministic Push-Down Automata due to the following reasons.
·
Non-Deterministic means a process that can
have more than one result even when its input is fixed. For example, if you
throw a coin with the same motion and strength, it is unlikely to get the same
result every time (Heads or Tails).
·
Non-Deterministic Push-Down Automata are
like Finite Automata, except they also have a stack memory where they can store
an arbitrary amount of information.
·
Non-Deterministic Push-Down Automata can
accept the context-free languages.
·
Non-deterministic Push-Down Automata can
have more than one move from a state on an input symbol and stack symbol.
·
It is not always possible to convert Non-Deterministic
Push-Down Automata to Deterministic Push-Down Automata.
·
Expressive Power of Non-deterministic PDA
is more as compared to expressive deterministic PDA.
SUBSCRIBE, SHARE, LIKE AND COMMENTS FOR MORE UPDATES
KINDLY, DON’T COPY PASTE
SEND WHATSAPP OR E-MAIL FOR ANY QUERY
0325-6644800
kamranhameedvu@gmail.com