Theory of Computation
Theory of Computation
  • 41
  • 811 133
Rice's theorem
Rice's theorem
Переглядів: 39 360

Відео

Introduction to Computational Complexity Theory
Переглядів 14 тис.8 років тому
Introduction to Computational Complexity Theory
More on the class NP
Переглядів 7 тис.8 років тому
More on the class NP
NP-Completeness
Переглядів 7 тис.8 років тому
NP-Completeness
More on NP-Completeness
Переглядів 6 тис.8 років тому
More on NP-Completeness
Undecidability
Переглядів 18 тис.8 років тому
Undecidability
Decidability properties of Regular and Context Free Languages
Переглядів 16 тис.8 років тому
Decidability properties of Regular and Context Free Languages
More on Undecidability
Переглядів 10 тис.8 років тому
More on Undecidability
Reduction
Переглядів 13 тис.8 років тому
Reduction
Applications of Reduction
Переглядів 7 тис.8 років тому
Applications of Reduction
Turing Machine
Переглядів 16 тис.8 років тому
Turing Machine
More on Turing Machine
Переглядів 11 тис.8 років тому
More on Turing Machine
Non deterministic Turing Machine Edit Lesson
Переглядів 11 тис.8 років тому
Non deterministic Turing Machine Edit Lesson
Configuration Graphs
Переглядів 8 тис.8 років тому
Configuration Graphs
Closure Properties of Decidable and Turing recognizable languages
Переглядів 16 тис.8 років тому
Closure Properties of Decidable and Turing recognizable languages
Pushdown Automata
Переглядів 12 тис.8 років тому
Pushdown Automata
Deterministic Context Free Languages
Переглядів 10 тис.8 років тому
Deterministic Context Free Languages
Closure Properties of CFLs
Переглядів 10 тис.8 років тому
Closure Properties of CFLs
Pushdown Automata - Examples and Relation with CFGs
Переглядів 12 тис.8 років тому
Pushdown Automata - Examples and Relation with CFGs
Pushdown Automata - Definition and Example
Переглядів 11 тис.8 років тому
Pushdown Automata - Definition and Example
Examples of non- CFLs
Переглядів 8 тис.8 років тому
Examples of non- CFLs
Examples of CFGs, Reg subset of CFL
Переглядів 13 тис.8 років тому
Examples of CFGs, Reg subset of CFL
Parse tree, derivation, ambiguity
Переглядів 13 тис.8 років тому
Parse tree, derivation, ambiguity
Normal forms, Chomsky normal form
Переглядів 12 тис.8 років тому
Normal forms, Chomsky normal form
Non-CFLs, pumping lemma
Переглядів 11 тис.8 років тому
Non-CFLs, pumping lemma
Introduction to CFGs
Переглядів 15 тис.8 років тому
Introduction to CFGs
DFA minimization
Переглядів 12 тис.8 років тому
DFA minimization
Examples of non-regular languages
Переглядів 14 тис.8 років тому
Examples of non-regular languages
Equivalence of NFA and DFA, Closure properties
Переглядів 33 тис.8 років тому
Equivalence of NFA and DFA, Closure properties
Regular expressions
Переглядів 20 тис.8 років тому
Regular expressions

КОМЕНТАРІ

  • @iamhit45
    @iamhit45 2 місяці тому

    my toc lecturer sheeraz recommended to watch these but i didn't understand a bit.iam from NIT Calicut hi to all of the students suffering

  • @shashankvashishtha4454
    @shashankvashishtha4454 2 місяці тому

    no majak masti, kabhi hastay nahi, very boring. Hate that.

  • @bir4y416
    @bir4y416 3 місяці тому

    this is a wonderful lecture, awesome handwriting as well

  • @rajputadi01
    @rajputadi01 3 місяці тому

    the cameraman smoked something from 29:00

  • @harshi-cm6zn
    @harshi-cm6zn 4 місяці тому

    is + shown is union operator?

  • @kapilgupta5928
    @kapilgupta5928 4 місяці тому

    I wanted to attempt to prove the closure of RL on homomorphism using ideas of GNFA. But stuck on the statement "Does all finite languages (with number of strings) are always an element of RL? What about infinite length string in a finite set of strings? Does absurd patterns of infinite length string can be identifiable by DFA?"

  • @ShrutiBachal
    @ShrutiBachal 4 місяці тому

    The lecture contents are really helpful. I have completed the whole session and it was a great experience to study TOC in a simplified way. Thank you sir!

  • @GursimarSinghMiglani
    @GursimarSinghMiglani 6 місяців тому

    .ll

  • @bpn333
    @bpn333 6 місяців тому

    i just hate how my college forces me to watch this from swayam portal removing normal classes and normal exams altogether.

    • @atharvchavan544
      @atharvchavan544 6 місяців тому

      you are lucky

    • @bpn333
      @bpn333 6 місяців тому

      @@atharvchavan544 bro exam dena padta he. Aur padai ke naam pe 8 saal purana video chod rahe he.

  • @thendimension4816
    @thendimension4816 7 місяців тому

    The teacher we need, but we don't deserve.

  • @oogieboo1
    @oogieboo1 7 місяців тому

    For the recognizable languages, kleene star will loop infinitely and fail if you run sequentially if done using your method.

  • @hara128
    @hara128 7 місяців тому

    this is a very well explained video and this is the quality of lectures every child should receive ... kudos to ur explanation sir!!

  • @Hades-su8sf
    @Hades-su8sf 8 місяців тому

    for all 'x' belonging to sigma* also mean x can be epsilon, for which |x| = 0. so how is t(0) computed as 't' maps natural number to natural number but 0 is not a natural number.

  • @JakeSilver26
    @JakeSilver26 8 місяців тому

    you are the goat

  • @madalitsomuwawa88
    @madalitsomuwawa88 10 місяців тому

    mmakwana fada

  • @kira-nr3qj
    @kira-nr3qj Рік тому

    sir i have a doubt in construction of nfa for the star operation, i think we have to also cover the case when string is epsilon, as it is present in the star of two languages.

  • @JacobPeralta21
    @JacobPeralta21 Рік тому

    n> o string form will accepted, not n >= 0 i guess..

  • @ujjwal770
    @ujjwal770 Рік тому

    t

  • @anarabiyev9766
    @anarabiyev9766 Рік тому

    Hello, sir. You content is great, if you make some thumbnails, edit titles and cover, edit video to speed up some writings, your channel will go to next level.

  • @thomaspanyasrivinit5473
    @thomaspanyasrivinit5473 Рік тому

    This lecture was super helpful! Thanks!

  • @NAMANMARKHEDKAR
    @NAMANMARKHEDKAR Рік тому

    Excellent lecture. Watching this playlist at the night before the exam . Thanks a lot

  • @giveaway4002
    @giveaway4002 Рік тому

    watching this 6th time.

  • @giveaway4002
    @giveaway4002 Рік тому

    its depressing we have Undecidability. there are problems which my TM can never ever solve :(

  • @giveaway4002
    @giveaway4002 Рік тому

    awesome

  • @aishwaryakasthala97
    @aishwaryakasthala97 Рік тому

    Nice explanation using those boxes to represent. Thank you Sir!

  • @AnupGupta-z9x
    @AnupGupta-z9x Рік тому

    kya padhate ho sir bhooot acchaa

  • @rijulsharma4453
    @rijulsharma4453 Рік тому

    Thank you sir for this informative and well-structured Lecture series.

  • @kapilgupta5928
    @kapilgupta5928 Рік тому

    Definitely, best lectures, some math is missing so that it is graspable to students. I noticed that at 14.09, where e-transitions are taken care, e-closure from q_0, starting state must also be cared. However, I feel that just a small mistake. If you go through Prof. Ullman's lecture, this mistake can be easily rectified.

  • @itsmevision38
    @itsmevision38 Рік тому

    best playlist of TOC

  • @snehalathareddy5566
    @snehalathareddy5566 Рік тому

    NPTEL MAKES ME TO FEEL LIKE I AM AN IIT STUDENT😊

  • @sayanghosh6996
    @sayanghosh6996 Рік тому

    This lecture should be re-recorded. too much confusion and nauseating camera work

  • @deepakmodi9343
    @deepakmodi9343 Рік тому

    I am very thankful that even though there are not any good teachers in my college, there are excellent teachers on youtube.

  • @sayanghosh6996
    @sayanghosh6996 Рік тому

    11:37 whoever edited this smooth-ass cut deserves a raise

  • @mauricio0guaruja
    @mauricio0guaruja Рік тому

    that opening soundtrack is just like twin peaks opening soundtrack

  • @ikramwani5207
    @ikramwani5207 Рік тому

    i m still stucka t reduction i cant understand reductions

    • @saranshsaini4870
      @saranshsaini4870 4 місяці тому

      exactly, understood everything except undecidability and reductions

  • @anupkumar-cy2dv
    @anupkumar-cy2dv Рік тому

    🙏

  • @dennyage4791
    @dennyage4791 2 роки тому

    Kitna bekar pdate ho aaap

  • @kunaldubey3152
    @kunaldubey3152 2 роки тому

    Thank you sir for explaining myhill nerode theorem so briefly.

  • @steveraphaelpulikottil5755
    @steveraphaelpulikottil5755 2 роки тому

    doesn't S->SB remove B->^ give S->S production which shall be eliminated as unit production?

  • @user-mv3cg7hi7g
    @user-mv3cg7hi7g 2 роки тому

    I love the intro music. very retro vibes. also great video.

  • @deveshparwani9087
    @deveshparwani9087 2 роки тому

    Thank you Sir, Love from NIT Kurukshetra. ❤

  • @chilliam65
    @chilliam65 2 роки тому

    Thank you! That was a very clear explanation

  • @devesh096
    @devesh096 2 роки тому

    Very Well Explained. Love from NIT Kurukshetra, MCA Dept. :)

  • @bijendersverma
    @bijendersverma 2 роки тому

    Thanks sir It is easy to understand when you explain

  • @GamingBoiiii
    @GamingBoiiii 2 роки тому

    COMPLETE SPPU SYLLABUS INCLUDED ?

  • @varunkumar3361
    @varunkumar3361 2 роки тому

    I think there should be an update of this course now, by the same professor. BTW this is an awesome course.

  • @bijendersverma
    @bijendersverma 2 роки тому

    Sir at 14:36 it must be 0 on the edge from q1 to q0 as explained by you.

  • @190_priyamsaha7
    @190_priyamsaha7 2 роки тому

    I think at 19:00 there is a little mistake . I think it should be (q0 , q1 , q0 , q0). Please Some Body verify my answer...

  • @deepjyoti7147
    @deepjyoti7147 2 роки тому

    7:02 mins u said Pen and paper is a computational device. Which is a completely false statement. If we write 1+2 on paper it ain't gonna give 3 as output by itself. We are the one who is writing the output 3 on paper after calculating the problem. How can a thing which has no computational power can be a computational device? We use pen and paper to note the current progress of the problem that doesn't mean pen and paper will become a computational device.

  • @djhi-tek9249
    @djhi-tek9249 2 роки тому

    Bashar al Asad 😲