Lecture 7: Decision Problems for Automata and Grammars

Name: Lecture 7: Decision Problems for Automata and Grammars
Uploaded: 2021-10-06T12:45:14Z
Duration: 1 h 16 min 51 s
Description: Description: Quickly reviewed last lecture. Showed the decidability of various problems about automata and grammars: \(A\) DFA , \(A\) NFA , \(E\) DFA , \(EQ\) DFA , and \(A\) CFG . Also showed that \(A\) TM is T-recognizable. Instructor: Prof. Michael Sipser

1:16:51

Up Next

Lecture 8: Undecidability

Continue

Description: Quickly reviewed last lecture. Showed the decidability of various problems about automata and grammars: \(A\)_DFA, \(A\)_NFA, \(E\)_DFA, \(EQ\)_DFA, and \(A\)_CFG. Also showed that \(A\)_TM is T-recognizable.

Instructor: Prof. Michael Sipser