CS402 GDB NO. 1 FALL 2022 || 100% RIGHT SOLUTION || THEORY OF AUTOMATA || BY VuTech

 

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={yy¹ where y¹ = 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