Theory Of Computation

بواسطة: Swayam

Overview

This is an introductory course on Theory of Computation intended for undergraduate students in computer science. In this course we will introduce various models of computation and study their power and limitations. We will also explore the properties of the corresponding language classes defined by these models and the relations between them. We will assume the student is comfortable in analytical reasoning and has preferably done a course on Data Structures and Algorithms.INTENDED AUDIENCE: Computer Science undergraduate students.PRE-REQUISITES:It is recommended that the candidate has done a course in Data Structures and Algorithms.INDUSTRY SUPPORT: Content will be updated soon

Syllabus

Week 1: Finite Automata – deterministic and nondeterministic, regular operationsWeek 2: Regular Expression, Equivalence of DFA, NFA and REs, closure propertiesWeek 3: Non regular languages and pumping lemma, DFA Minimization,Week 4: CFGs, Chomsky Normal FormWeek 5: Non CFLs and pumping lemma for CFLs, PDAs, Equivalence of PDA and CFGWeek 6: Properties of CFLs, DCFLs, Turing Machines and its variantsWeek 7: Configuration graph, closure properties of decidable languages, decidability properties of regular languages and CFLsWeek 8: Undecidability, reductions, Rice's Theorem, introduction to complexity theory

Taught by

Raghunath Tewari

Theory Of Computation
الذهاب الي الدورة

Theory Of Computation

بواسطة: Swayam

  • Swayam
  • مجانية
  • الإنجليزية
  • متاح شهادة
  • أيام محددة
  • الجميع
  • N/A
8.1.2PHP Version321msRequest Duration2MBMemory UsageGET ar/الدورات/{slug}Route
    • Booting (203ms)
    • Application (117ms)
    • 1 x Booting (63.28%)
      202.95ms
      1 x Application (36.47%)
      116.96ms
      14 templates were rendered
      • public.courses.show (resources/views/public/courses/show.blade.php)3bladefile
        Params
        0
        course
        1
        links
        2
        config
      • public.courses.partials.breadcrumbs (resources/views/public/courses/partials/breadcrumbs.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.heading (resources/views/public/courses/partials/heading.blade.php)7bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        classes
      • public.courses.partials.details (resources/views/public/courses/partials/details.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.breadcrumbs (resources/views/public/courses/partials/breadcrumbs.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.heading (resources/views/public/courses/partials/heading.blade.php)7bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        classes
      • public.layouts.main (resources/views/public/layouts/main.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.layouts.partials.meta (resources/views/public/layouts/partials/meta.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.layouts.partials.navbar (resources/views/public/layouts/partials/navbar.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.auth.profile.partials.links (resources/views/public/auth/profile/partials/links.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.layouts.partials.flash-session (resources/views/public/layouts/partials/flash-session.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      uri
      GET ar/الدورات/{slug}
      middleware
      web, localize:ar
      controller
      App\Http\Controllers\CourseController@show
      as
      ar.courses.show
      namespace
      prefix
      /ar
      where
      file
      app/Http/Controllers/CourseController.php:17-35
      6 statements were executed6.39ms
      • select * from `courses` where `slug_ar` = 'theory-of-computation' limit 1
        5.24ms/app/Http/Controllers/CourseController.php:20corspedia
        Metadata
        Bindings
        • 0. theory-of-computation
        Backtrace
        • 17. /app/Http/Controllers/CourseController.php:20
        • 18. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 19. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 20. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • update `courses` set `visitors` = `visitors` + 1, `courses`.`updated_at` = '2025-02-22 14:49:44' where `id` = 2508
        280μs/app/Http/Controllers/CourseController.php:21corspedia
        Metadata
        Bindings
        • 0. 2025-02-22 14:49:44
        • 1. 2508
        Backtrace
        • 17. /app/Http/Controllers/CourseController.php:21
        • 18. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 19. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 20. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select `id`, `name_en`, `name_ar`, `topic_id`, `slug_en`, `slug_ar` from `subjects` where `subjects`.`id` in (6)
        200μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select `id`, `name_en`, `name_ar`, `slug_en`, `slug_ar` from `topics` where `topics`.`id` in (1)
        190μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 25. /app/Http/Controllers/CourseController.php:23
        • 26. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 27. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 28. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 29. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `providers` where `providers`.`id` in (14) and `providers`.`deleted_at` is null
        230μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `html_files` where `html_files`.`id` = 2499 limit 1
        250μs/app/Models/Course.php:84corspedia
        Metadata
        Bindings
        • 0. 2499
        Backtrace
        • 21. /app/Models/Course.php:84
        • 28. view::public.courses.show:29
        • 30. /vendor/laravel/framework/src/Illuminate/Filesystem/Filesystem.php:125
        • 31. /vendor/laravel/framework/src/Illuminate/View/Engines/PhpEngine.php:58
        • 32. /vendor/laravel/framework/src/Illuminate/View/Engines/CompilerEngine.php:72
      App\Models\HtmlFile
      1
      App\Models\Provider
      1
      App\Models\Topic
      1
      App\Models\Subject
      1
      App\Models\Course
      1
        _token
        rg5MRwqzrAgmOy03BleIxTPqrJJrUq0Bni992Nye
        locale
        ar
        _previous
        array:1 [ "url" => "https://www.corspedia.com/ar/%D8%A7%D9%84%D8%AF%D9%88%D8%B1%D8%A7%D8%AA/theory...
        _flash
        array:2 [ "old" => [] "new" => [] ]
        PHPDEBUGBAR_STACK_DATA
        []
        path_info
        /ar/%D8%A7%D9%84%D8%AF%D9%88%D8%B1%D8%A7%D8%AA/theory-of-computation
        status_code
        200
        
        status_text
        OK
        format
        html
        content_type
        text/html; charset=UTF-8
        request_query
        []
        
        request_request
        []
        
        request_headers
        0 of 0
        array:24 [ "sec-ch-ua-mobile" => array:1 [ 0 => "?0" ] "sec-ch-ua" => array:1 [ 0 => ""HeadlessChrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"" ] "cache-control" => array:1 [ 0 => "no-cache" ] "pragma" => array:1 [ 0 => "no-cache" ] "cdn-loop" => array:1 [ 0 => "cloudflare; loops=1" ] "priority" => array:1 [ 0 => "u=0, i" ] "upgrade-insecure-requests" => array:1 [ 0 => "1" ] "user-agent" => array:1 [ 0 => "Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)" ] "cf-connecting-ip" => array:1 [ 0 => "18.191.70.86" ] "accept" => array:1 [ 0 => "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7" ] "sec-fetch-site" => array:1 [ 0 => "none" ] "cf-visitor" => array:1 [ 0 => "{"scheme":"https"}" ] "sec-fetch-mode" => array:1 [ 0 => "navigate" ] "sec-fetch-user" => array:1 [ 0 => "?1" ] "x-forwarded-proto" => array:1 [ 0 => "https" ] "cf-ipcountry" => array:1 [ 0 => "US" ] "accept-encoding" => array:1 [ 0 => "gzip, br" ] "sec-fetch-dest" => array:1 [ 0 => "document" ] "sec-ch-ua-platform" => array:1 [ 0 => ""Windows"" ] "x-forwarded-for" => array:1 [ 0 => "18.191.70.86" ] "cf-ray" => array:1 [ 0 => "915fc8d148c6e258-ORD" ] "host" => array:1 [ 0 => "www.corspedia.com" ] "content-length" => array:1 [ 0 => "" ] "content-type" => array:1 [ 0 => "" ] ]
        request_server
        0 of 0
        array:50 [ "USER" => "www-data" "HOME" => "/var/www" "HTTP_SEC_CH_UA_MOBILE" => "?0" "HTTP_SEC_CH_UA" => ""HeadlessChrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"" "HTTP_CACHE_CONTROL" => "no-cache" "HTTP_PRAGMA" => "no-cache" "HTTP_CDN_LOOP" => "cloudflare; loops=1" "HTTP_PRIORITY" => "u=0, i" "HTTP_UPGRADE_INSECURE_REQUESTS" => "1" "HTTP_USER_AGENT" => "Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)" "HTTP_CF_CONNECTING_IP" => "18.191.70.86" "HTTP_ACCEPT" => "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7" "HTTP_SEC_FETCH_SITE" => "none" "HTTP_CF_VISITOR" => "{"scheme":"https"}" "HTTP_SEC_FETCH_MODE" => "navigate" "HTTP_SEC_FETCH_USER" => "?1" "HTTP_X_FORWARDED_PROTO" => "https" "HTTP_CF_IPCOUNTRY" => "US" "HTTP_ACCEPT_ENCODING" => "gzip, br" "HTTP_SEC_FETCH_DEST" => "document" "HTTP_SEC_CH_UA_PLATFORM" => ""Windows"" "HTTP_X_FORWARDED_FOR" => "18.191.70.86" "HTTP_CF_RAY" => "915fc8d148c6e258-ORD" "HTTP_HOST" => "www.corspedia.com" "REDIRECT_STATUS" => "200" "SERVER_NAME" => "corspedia.com" "SERVER_PORT" => "443" "SERVER_ADDR" => "141.95.147.152" "REMOTE_USER" => "" "REMOTE_PORT" => "47826" "REMOTE_ADDR" => "172.70.100.219" "SERVER_SOFTWARE" => "nginx/1.18.0" "GATEWAY_INTERFACE" => "CGI/1.1" "HTTPS" => "on" "REQUEST_SCHEME" => "https" "SERVER_PROTOCOL" => "HTTP/2.0" "DOCUMENT_ROOT" => "/var/www/corspedia/public" "DOCUMENT_URI" => "/index.php" "REQUEST_URI" => "/ar/%D8%A7%D9%84%D8%AF%D9%88%D8%B1%D8%A7%D8%AA/theory-of-computation" "SCRIPT_NAME" => "/index.php" "CONTENT_LENGTH" => "" "CONTENT_TYPE" => "" "REQUEST_METHOD" => "GET" "QUERY_STRING" => "" "SCRIPT_FILENAME" => "/var/www/corspedia/public/index.php" "PATH_INFO" => "" "FCGI_ROLE" => "RESPONDER" "PHP_SELF" => "/index.php" "REQUEST_TIME_FLOAT" => 1740235784.1353 "REQUEST_TIME" => 1740235784 ]
        request_cookies
        []
        
        response_headers
        0 of 0
        array:5 [ "content-type" => array:1 [ 0 => "text/html; charset=UTF-8" ] "cache-control" => array:1 [ 0 => "no-cache, private" ] "date" => array:1 [ 0 => "Sat, 22 Feb 2025 14:49:44 GMT" ] "set-cookie" => array:2 [ 0 => "XSRF-TOKEN=eyJpdiI6IkEzdTNvRmxWRmVkM2NzcDhEWFRoVmc9PSIsInZhbHVlIjoiZVVZZyt1UC9HY1JHejRnUWovSDlDbUpWN1c5dmdHeXcwMHJpcVN0djMyWnFSR2k3NXJZbjJiQTJ3dDMvUG5adkhQS0NSeUxHVC9FN01CZDhnUE9qenNNTVE5d0pBUzE5NlhpNllWU0l2aEZwblVoaEZGbkRBb1VZNVl3amlHc20iLCJtYWMiOiJjMGVhYjc5MTJmZGIxMThiMzU5YmExYjNiMDNmNDk2MTdiYjBiNTQ4ZjYwMmI1MjI4YTkzNDQ4ZmM1ZjBiNzMwIiwidGFnIjoiIn0%3D; expires=Sat, 22 Feb 2025 16:49:44 GMT; Max-Age=7200; path=/; samesite=laxXSRF-TOKEN=eyJpdiI6IkEzdTNvRmxWRmVkM2NzcDhEWFRoVmc9PSIsInZhbHVlIjoiZVVZZyt1UC9HY1JHejRnUWovSDlDbUpWN1c5dmdHeXcwMHJpcVN0djMyWnFSR2k3NXJZbjJiQTJ3dDMvUG5adkhQS0NSe" 1 => "laravel_session=eyJpdiI6ImdPOTZnelRhTmtBZGZYTHZYMCsrNlE9PSIsInZhbHVlIjoidmE4d01XMTdibmNtR2xsbGsvMWJQSThxbHp0eEMrRTZzM2xabkl3SDR0a1JOeFFZUUhoTUNrWEZWcWdZNjM5VWNhN3pFVVFReFJlMElPL0dxU0lMTVB4cytXRXhhSUVNdGxaRXVKb2wvTUNhRW9nd2t0TTBzMTlRNEI1MVRpajciLCJtYWMiOiI1MmVhNjI1ODdhNDFiZWRlY2Q3NWM4MWFiYjdiOTM5OTNiZmNjZjQ5YmRiZGUzMGZjZTA3YjE1NTA0MmE2MTQ0IiwidGFnIjoiIn0%3D; expires=Sat, 22 Feb 2025 16:49:44 GMT; Max-Age=7200; path=/; httponly; samesite=laxlaravel_session=eyJpdiI6ImdPOTZnelRhTmtBZGZYTHZYMCsrNlE9PSIsInZhbHVlIjoidmE4d01XMTdibmNtR2xsbGsvMWJQSThxbHp0eEMrRTZzM2xabkl3SDR0a1JOeFFZUUhoTUNrWEZWcWdZNjM5VWNh" ] "Set-Cookie" => array:2 [ 0 => "XSRF-TOKEN=eyJpdiI6IkEzdTNvRmxWRmVkM2NzcDhEWFRoVmc9PSIsInZhbHVlIjoiZVVZZyt1UC9HY1JHejRnUWovSDlDbUpWN1c5dmdHeXcwMHJpcVN0djMyWnFSR2k3NXJZbjJiQTJ3dDMvUG5adkhQS0NSeUxHVC9FN01CZDhnUE9qenNNTVE5d0pBUzE5NlhpNllWU0l2aEZwblVoaEZGbkRBb1VZNVl3amlHc20iLCJtYWMiOiJjMGVhYjc5MTJmZGIxMThiMzU5YmExYjNiMDNmNDk2MTdiYjBiNTQ4ZjYwMmI1MjI4YTkzNDQ4ZmM1ZjBiNzMwIiwidGFnIjoiIn0%3D; expires=Sat, 22-Feb-2025 16:49:44 GMT; path=/XSRF-TOKEN=eyJpdiI6IkEzdTNvRmxWRmVkM2NzcDhEWFRoVmc9PSIsInZhbHVlIjoiZVVZZyt1UC9HY1JHejRnUWovSDlDbUpWN1c5dmdHeXcwMHJpcVN0djMyWnFSR2k3NXJZbjJiQTJ3dDMvUG5adkhQS0NSe" 1 => "laravel_session=eyJpdiI6ImdPOTZnelRhTmtBZGZYTHZYMCsrNlE9PSIsInZhbHVlIjoidmE4d01XMTdibmNtR2xsbGsvMWJQSThxbHp0eEMrRTZzM2xabkl3SDR0a1JOeFFZUUhoTUNrWEZWcWdZNjM5VWNhN3pFVVFReFJlMElPL0dxU0lMTVB4cytXRXhhSUVNdGxaRXVKb2wvTUNhRW9nd2t0TTBzMTlRNEI1MVRpajciLCJtYWMiOiI1MmVhNjI1ODdhNDFiZWRlY2Q3NWM4MWFiYjdiOTM5OTNiZmNjZjQ5YmRiZGUzMGZjZTA3YjE1NTA0MmE2MTQ0IiwidGFnIjoiIn0%3D; expires=Sat, 22-Feb-2025 16:49:44 GMT; path=/; httponlylaravel_session=eyJpdiI6ImdPOTZnelRhTmtBZGZYTHZYMCsrNlE9PSIsInZhbHVlIjoidmE4d01XMTdibmNtR2xsbGsvMWJQSThxbHp0eEMrRTZzM2xabkl3SDR0a1JOeFFZUUhoTUNrWEZWcWdZNjM5VWNh" ] ]
        session_attributes
        0 of 0
        array:5 [ "_token" => "rg5MRwqzrAgmOy03BleIxTPqrJJrUq0Bni992Nye" "locale" => "ar" "_previous" => array:1 [ "url" => "https://www.corspedia.com/ar/%D8%A7%D9%84%D8%AF%D9%88%D8%B1%D8%A7%D8%AA/theory-of-computation" ] "_flash" => array:2 [ "old" => [] "new" => [] ] "PHPDEBUGBAR_STACK_DATA" => [] ]