Instantaneous Descriptions, Language of a Pushdown Automaton (Theory of Computing)
In today's lecture, we learn how we can describe the language of a pushdown automaton. To do this, we explore the concept of an instantaneous description, which is a more generalized way to describe the present configuration of a machine model.
31:48 There is a typo: The PDA rejects if for every sequence of (valid) moves, either P consumes w on some ID and fails to find an accepting ID, or it fails to consume all of w and all (valid) moves are exhausted. It is technically possible for the PDA to never stop executing. Use of "otherwise" here is somewhat misleading (you'd never want a PDA that loops forever, which was the context I wrote this).
Time Stamps:
0:00 Instantaneous Descriptions and Pushdown Automata
7:15 Example of how it works, graphically.
15:09 Formal definition of a "move" (zero or more) for a PDA, using instantaneous descriptions. Examples of usage.
27:40 Language of a Pushdown Automaton
32:36 Closing
Have a beautiful day!
Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
Draikou
Patreon Supporters (Basic Support):
Eric R
Patreon Supporters (Supporter Access!):
-----------------------------------------------------------
Become a supporter today! To support my work and mission to provide free or accessible Computer Science education (especially in theory), subscribe to the channel, share my videos. Please donate and contribute to support my work for more content:
PATREON: / pagewizard
SUBSCRIBESTAR: https://www.subscribestar.com/drpage
PAYPAL: https://paypal.me/pagewizard
Follow also at:
FACEBOOK: / danielrpage
TWITTER: / pagewizardgle
QUORA: https://www.quora.com/profile/Daniel-...
TWITCH: / pagewizard
#ComputerScience
#theoryofcomputing
#automatatheory