Sipser: Section 4.1
From CSWiki
CSC 341:Front Door | CSC 341: Cooperative commentary | Sipser:_Chapter_4
Contents |
Summary
This section groups the languages previously discussed and describes their relationships. Sipser builds Turing machines to solve problems regarding these languages. All the languages from previous chapters are Turing-recognizable.
Decidability of regular languages
Sipser starts with problems concerning regular languages. Two types of problems are discussed: acceptance problem and emptiness testing problem.
Deterministic Finite Automata
The problem ADFA asks whether a DFA accepts a given string. (page 166)
Theorem 4.1 ADFA is a decidable language.
The problem EDFA asks whether a finite automaton accepts any strings at all. (page 168)
Theorem 4.4 EDFA is a decidable language.
The problem EQDFA asks whether two DFAs recognize the same language. (page 169)
Theorem 4.5 EQDFA is a decidable language.
Non-deterministic Finite Automata
The problem ANFA asks whether a NFA accepts a given string. (page 167)
Theorem 4.2 ANFA is a decidable language.
Regular Expression
The problem AREX asks whether a regular expression generates certain string. (page 168)
Theorem 4.3 AREX is a decidable language.
Decidability of context-free languages
Sipser then tackles Context-free Languages, asking the same acceptance and emptiness problems.
Context-free Grammar
The problem ACFG asks whether a CFG generates a certain string. (page 170)
Theorem 4.7 ACFG is a decidable language.
The problem ECFG asks whether a CFG generates any string at all. (page 171)
Theorem 4.8 ECFG is a decidable language.
Theorem 4.9 Every context-free language is decidable.
Relationship among languages
regular languages 
context-free languages decidable languages Turing-recognizable languages
Each of these inclusions is known to be proper.
A reminder: Deciders Vs. Recognizers
A recognizer may take a TM, M, and a string, w and accepts if M accepts w, rejects if M rejects, or fails to terminate if M fails to do so.
A decider is similar in its return values, but must terminate ("halt"), returning either accept or reject.
CSC 341:Front Door | CSC 341: Cooperative commentary Sipser:_Chapter_4 |
