CSE237 Lecture 20, Fall 2006

Lecture 20 (Decidable Languages), 4/05/06

Concepts, definitions (in italics):

The specifications (encoding) for any DFA is a string; the set of specifications for all DFAs is therefore a set of strings (a language). Same is true of any NFA / RE / PDA / CFG / TM.
The languages A-DFA, A-NFA, A-REX are decideable.
Problem (algorithm) A reduces to B: the solution for B is used to help solve A; can use the decider/recognizer for B to help create decider/recognizer for A
Reduction of A to B: an algorithm for A that makes use of B (as subroutine)
Claim: A DFA's language is not empty if and only if there is a path from the initial state to some final state.
An algorithm for deciding if a given DFA accepts an empty language.
The languages E-DFA, E-NFA, E-REX are decideable.

Reading:

Skills:

Notes:

A language is decidable there exists an algorithm that determines, for any string, whether or not it is in the language.
ADFA = {(<M>, w) : M is a DFA that accepts w}
ANFA= {(<M>, w) : M is a NFA that accepts w}
AREX= {(X,W) : w is a regular expression that generates w}
They are all decidable
ADFA-decider would do the following on input (,w):

1) If this input is not properly formatted we reject
2) Simulate B on w
3) If you end up in a FINAL state, accept; else reject

1) Syntax check, reject if fails
2) C = NFA_DFA_Converter ()
3) return DFA_Simulator (C)

1) Syntax check, reject if fails
2) C = RE_NFA_converter (x)
3) Return A_NFA_decider (C,w)

EDFA = {: is a valid DFA specification where L(B) = Ų}
ENFA = {: is a valid NFA specification where L(B) = Ų}

EREX = {X: is a valid Reg.exp specification where L(X) = Ų}
They are all decidable
The language of a given DFA/NFA/RE is empty if and only if there do not exist any strings accepted (generated) by this DFA/NFA/RE. If there exists any string accepted (generated) by this DFA/NFA/RE, then its language is not empty.
The algorithm for deciding EDFA relies on the following fact:
A DFA's language is not empty if and only if there is a path from the initial state to some final state.

1) syntax check, reject if fails
2) M = NFA_DFA_converter ()
3) Return EDFA-decider (M)

1) syntax check, reject if fails
2) M = RE_NFA_converter(X)
3) Return ENFA-decider(M)