The Gateway to Computer Science Excellence
60 views

$$\textbf{Contents}$$

$\textbf{Syllabus:}$

Web Page

Regular expressions and finite automata, Context-free grammars and push-down automata, Regular and context-free languages, Pumping lemma, Turing machines and undecidability.

$$\small{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count}&2&2&2&3&3&3&2&2.5&3
\\\hline\textbf{2 Marks Count}&3&3&5&3&3&3&3&3.3&5
\\\hline\textbf{Total Marks}&8&8&12&9&9&9&\bf{8}&\bf{9.2}&\bf{12}\\\hline
\end{array}}}$$

            Topic Covered in Videos Video link from GO Youtube channel
  • Introduction to TOC and Finite State Machines
  • Closure & Non-determinism
  • Pumping Lemma
  • Minimizing Finite State Machines
  • Context-free Grammars
  • Relationship to Compiling & Chomsky Normal Forms
  • Deterministic & Non-deterministic Pushdown Automata
  • Context-Free Grammars (CFGs) and Push Down Automata (PDA)
  • More Lemmas and CYK Algorithm
  • Undecidability and CFLs
  • The Bull's Eye
  • Turing Machines
  • The Halting Problem
  • Decidability
  • Complexity Theory; Quantified Boolean Formula
  • Decidability discussion Part 1
  • Decidability discussion Part 2
  • Decidability discussion Part 3
GO Videos

Topics to be Covered:

posted Oct 7 in Study Materials by Veteran (52,769 points)
edited Oct 7 by | 60 views
2
Like
0
Love
0
Haha
0
Wow
0
Angry
0
Sad
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,662 questions
56,122 answers
193,629 comments
93,031 users