CMPT 125 Lecture Notes - Lecture 23: Regular Expression, Halting Problem

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 125
• Professor: Igor Shinkar

Document Summary

Theorem: a language l is regular if and only if there exists a regular expression defining l. For every dfa there exists a regexp defining it. For every regexp there exists a dfa defining it. Theorem: there is no dfa that accepts l. Decide(l): given an input x, decide whether x belongs to l. Surprising fact: there are languages that are not decidable, i. e. , there is no algorithm that solves. A decision algorithm a gets an input x and outputs yes or no . Halts for every input and outputs yes or no . Define lang(a) to be the set of all x"s for which a(x)= yes . We pose *no restrictions* of the resources that a is allowed to use. Theorem: there exists l that cannot be decided by any algorithm. In other words: for any algorithm a: either lang(a) = a or a does not halt on some (all) inputs. Input: a program p and an input x.