▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com
▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=c-IoxIZFeRQ
Here we look at "simple" machines, and create one that checks whether the length of the given input is even or not. We consider how many states are needed, as well as the start state, and how to connect the states together. We conclude with another example as "homework".
Contribute:
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Live Streaming (Saturdays, Sundays 2PM GMT):
Twitch: https://www.twitch.tv/easytheory
(Youtube also)
Mixer: https://mixer.com/easytheory
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ADDITIONAL QUESTIONS◀
1. What does the machine given at the end do?
2. Can you make the machine at the end "simpler" in terms of number of states?
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental theory of computer science. It sets out to define, mathematically, what exactly computation is, what is feasible to solve using a computer, and also what is not possible to solve using a computer. The main objective is to define a computer mathematically, without the reliance on real-world computers, hardware or software, or the plethora of programming languages we have in use today. The notion of a Turing machine serves this purpose and defines what we believe is the crux of all computable functions.
This channel is also about weaker forms of computation, concentrating on two classes: regular languages and context-free languages. These two models help understand what we can do with restricted means of computation, and offer a rich theory using which you can hone your mathematical skills in reasoning with simple machines and the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them are tractable, i.e. we can build efficient algorithms to reason with objects such as finite automata, context-free grammars and pushdown automata. For example, we can model a piece of hardware (a circuit) as a finite-state system and solve whether the circuit satisfies a property (like wh
...
https://www.youtube.com/watch?v=WWg_28jrmGw
Here we look at the question of how many DFAs with 3 states and unary alphabet (Σ = {0}) are possible. It turns out to be a somewhat surprising answer. We first calculate the number of possible DFAs, and then turn to the question of how many *different* regular languages are possible. Then we break this down into cases, depending on how many states are final and how many of those are reachable from the start state. We then can eliminate more cases by noting that DFAs that are just complements of each other (final states and non-final states flipped) only need to be considered once.
Patreon: https://www.patreon.com/easytheory
Facebook: https://www.facebook.com/easytheory/
Twitter: https://twitter.com/EasyTheory
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ADDITIONAL QUESTIONS◀
1. What about for four-state DFAs?
2. What about two-state DFAs but Σ = {0, 1}?
3. What about three-state NFAs with Σ = {0}?
4. Is there a general formula for the number of DFAs with n states and an alphabet of size k?
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental theory of computer science. It sets out to define, mathematically, what exactly computation is, what is feasible to solve using a computer, and also what is not possible to solve using a computer. The main objective is to define a computer mathematically, without the reliance on real-world computers, hardware or software, or the plethora of programming languages we have in use today. The notion of a Turing machine serves this purpose and defines what we believe is the crux of all computable functions.
This channel is also about weaker forms of computation, concentrating on two classes: regular languages and context-free languages. These two models help understand what we can do with restricted means of computation, and offer a rich theory using which you can hone your mathematical skills in reasoning with simple machines and the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them are tractable, i.e. we can build efficient algorithms to reason with objects such as finite automata, context-free grammars and pushdown automata. For example, we can model a piece of hardware (a circuit) as a finite-state system and solve whether the circuit satisfies a property (like whether it performs ad
...
https://www.youtube.com/watch?v=R9C9YiMNrFE
Here we show that the set of strings that represent perfect squares is not regular by using the pumping lemma for regular languages. The "trick" here is to look at the resulting string length and show that it can only be between two consecutive perfect squares, and not equal to either of them.
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=Au8vH07IXuM
Full Theory of Computation Lecture playlist: https://www.youtube.com/watch?v=OPaB-rpKhZ0&list=PLylTVsqZiRXMiTARmrsxCWU2RahyKB_Ae&index=1&t=1s
Lecture "a la carte" playlist: https://www.youtube.com/watch?v=gO9Ho9Dpu8k&list=PLylTVsqZiRXP51EfJWv8cxD6wIFTZQD9_&index=1
Here we formalize the notion of a DFA computation, meaning what states are entered on a given string. We also define what an accepting computation is.
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=PHihJd-G7cc
Here we show that the union of two given context-free languages, {0^n 1^n 2^m 3^m} Union {0^n 1^m 2^m 3^n}, is also a context-free language. We give a context-free grammar for each of them, and derive a context-free grammar for their union.
Patreon: https://www.patreon.com/easytheory
Facebook: https://www.facebook.com/easytheory/
Twitter: https://twitter.com/EasyTheory
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ADDITIONAL QUESTIONS◀
1. Would this work for the intersection of the two languages?
2. What about {0^n 1^m 2^n 3^m}?
3. Is this the smallest CFG for this language?
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental
theory of computer science. It sets out to define, mathematically, what
exactly computation is, what is feasible to solve using a computer,
and also what is not possible to solve using a computer.
The main objective is to define a computer mathematically, without the
reliance on real-world computers, hardware or software, or the plethora
of programming languages we have in use today. The notion of a Turing
machine serves this purpose and defines what we believe is the crux of
all computable functions.
This channel is also about weaker forms of computation, concentrating on
two classes: regular languages and context-free languages. These two
models help understand what we can do with restricted
means of computation, and offer a rich theory using which you can
hone your mathematical skills in reasoning with simple machines and
the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them
are tractable, i.e. we can build efficient algorithms to reason
with objects such as finite automata, context-free grammars and
pushdown automata. For example, we can model a piece of hardware (a circuit)
as a finite-state system and solve whether the circuit satisfies a property
(like whether it performs addition of 16-bit registers correctly).
We can model the syntax of a programming language using a grammar, and
build algorithms that check if a string parses according to this grammar.
On the other hand, most problems that ask properties about Turing machines
are undecidable.
This Youtube channel will help you see and prove that several tasks involving Turing machines are unsolvable---i.e., no computer, no software, can so
...
https://www.youtube.com/watch?v=zM3bKd-9334
Here we define the language of a DFA, which is the set of all strings that it accepts. Then we look at an example DFA, and try to discern what language it has. We produce some example strings that it accepts, and then see the pattern that it accepts exactly the strings that have a length a multiple of 3 plus 1.
Contribute:
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Live Streaming (Saturdays, Sundays 2PM GMT):
Twitch: https://www.twitch.tv/easytheory
(Youtube also)
Mixer: https://mixer.com/easytheory
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ADDITIONAL QUESTIONS◀
1. Design a DFA with language of all strings w in {0, 1}* that start and end with a 0, or start and end with a 1, or is epsilon. (Super hard: what if w was in {0, 1, 2}*?)
2. Design a DFA with language of all strings in {0, 1}* that contain 111 as a substring.
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
▶ABOUT THIS CHANNEL◀
The theory of computation is perhaps the fundamental theory of computer science. It sets out to define, mathematically, what exactly computation is, what is feasible to solve using a computer, and also what is not possible to solve using a computer. The main objective is to define a computer mathematically, without the reliance on real-world computers, hardware or software, or the plethora of programming languages we have in use today. The notion of a Turing machine serves this purpose and defines what we believe is the crux of all computable functions.
This channel is also about weaker forms of computation, concentrating on two classes: regular languages and context-free languages. These two models help understand what we can do with restricted means of computation, and offer a rich theory using which you can hone your mathematical skills in reasoning with simple machines and the languages they define.
However, they are not simply there as a weak form of computation--the most attractive aspect of them is that problems formulated on them are tractable, i.e. we can build efficient algorithms to reason with objects such as finite automata, context-f
...
https://www.youtube.com/watch?v=D12PEIQhH1A
Here we prove the recursion theorem, which is one of the most important results in computability theory. This informally shows that any Turing Machine can "obtain" its own description on the tape, and then compute something with it. This video follows Sipser's presentation of the recursion theorem, with slight alterations to make understanding easier. The recursion theorem is not super difficult to show, but it gives the theorist a strong tool to show that many languages are undecidable, not recognizable, or even not computable in only a few lines.
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su
Timeline:
0:00 - Intro
0:15 - Informal Description of Recursion Theorem
1:29 - The convert_to_TM function
3:50 - Construction of the SELF Turing Machine
10:15 - Formal Statement of Recursion Theorem
12:26 - Proof of the Recursion Theorem
17:45 - Example 1: A_TM is not Decidable
20:23 - Example 2: MIN_TM is not Recognizable
What is a Turing Machine? It is a state machine that has a set of states, input, tape alphabet, a start state, exactly one accept state, and exactly one reject state. See https://www.youtube.com/watch?v=j0bIxPqlYLE&ab_channel=EasyTheory for more details.
▶CONTRIBUTE◀
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=iXpp5X6WPkE
Here we show that a finite number of strings added or removed from any language will not change the main "property" of the language.
Easy Theory Website: https://www.easytheory.org
Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: https://www.patreon.com/easytheory
Discord: https://discord.gg/SD4U3hs
#easytheory
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
...
https://www.youtube.com/watch?v=sXoLZCtYHAE
Here we show that the language {0^n 1^n : n at least 0} is not regular using a direct proof. We assumed that a DFA exists, and then derive a contradiction purely based on the fact that the DFA must repeat a "long enough" string. If we choose the string carefully, we can derive a string that the DFA accepts but is not in the language. Therefore, the language is not regular.
One could use the pumping lemma for regular languages, but this direct proof I think is more easily understood compared to a mechanical proof structure like that technique.
What is the pumping lemma for regular languages? It is a way to help prove that certain languages are not regular (i.e., those languages accepted by a DFA). If a language is regular, then it has certain properties; on the other hand, if it does not have those properties, then it cannot be regular. See https://www.youtube.com/watch?v=x2J5kaf6gjg&ab_channel=EasyTheory for more details.
Patreon: https://www.patreon.com/easytheory
If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1
▶ADDITIONAL QUESTIONS◀
1. Prove that the language of all strings with the same number of 0s and 1s is not regular (note: this isn't 0^n 1^n!).
2. (Hard) Prove that the language of all strings with the same number of 01s and 10s with alphabet {0, 1, 2} is not regular (note: if the alphabet is {0, 1}, it is regular!).
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.
...
https://www.youtube.com/watch?v=5GG8goBW9gw