CSci 301 Lecture Notes

Week Six, Tuesday: Decidable Languages

Decidable Problems Concerning Regular Languages

Theorem 4.2: A_NFA is a decidable language.

Theorem 4.3: A_REX is a decidable language.

Theorem 4.4: E_DFA is a decidable language.

Theorem 4.5: EQ_DFA is a decidable language.

Decidable Problems Concerning Context-Free Languages

Theorem 4.7: E_DFA is a decidable language.

Theorem 4.8: Every context-free language is decidable.

• CS 301 Theory of Computation Syllabus

• CS 301 Theory of Computation

• Computer Science

• Science

• Home

notes06a.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by Rick Wagner. Copyright © 1998-2011, all rights reserved.