CS计算机代考程序代写 python Context Free Languages algorithm FIT2014 Theory of Computation Lecture 20 University

FIT2014 Theory of Computation Lecture 20 University
Faculty of Information Technology

FIT2014 Theory of Computation

Lecture 20
Decidability

slides by
based in part on previous slides by

COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969

Warning
This material has been reproduced and communicated to you by or on behalf of Monash University

in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.

Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.

1 / 18

Overview

I Decision problems

I Decidable problems and languages

I Deciders

I Closure

2 / 18

Deciders

Reminder:

A decider is a Turing Machine that halts for every input.

A language is decidable if it is Accept(L) for some decider.

. . . in which case, its complement is Reject(L) for the same decider.

Examples:

I Regular Languages

I Context Free Languages

I {anbnan : n ≥ 0}

3 / 18

Decidable: synonyms

decidable

= recursive

= solvable

= computable

. . . sometimes, though “computable” has
been used with other meanings too.

4 / 18

Decision Problems

Input: an integer
Question: Is it even?

Input: a string.
Question: Is it a palindrome?

Input: an expression in propositional logic
Question: Is it ever True?

Input: a graph G , and two vertices s and t
Question: is there a path from s to t in G ?

Input: a Python program
Question: is it syntactically correct?

5 / 18

Input: a Finite Automaton
Question: Does it define the empty language?

Input: two Regular Expressions
Question: Do they define the same language?

Input: a Finite Automaton
Question: Does it define an infinite language?

Input: a Context Free Grammar
Question: Does it define the empty language?

Input: a Context Free Grammar
Question: Does it generate an infinite language?

Input: a Context Free Grammar and a string w
Question: Can w be generated by the grammar?

6 / 18

Decision Problems
A decision problem is a problem where, for each input, the answer is Yes or No.

A decider solves a decision problem if it
I Accepts an input for which the answer is Yes, and
I Rejects any input for which the answer is No.

Decision problem −→ language
I { YES-inputs }

Language −→ decision problem
I Input: a string

(over some alphabet, usually representing some object)
Question: Is the string in the Language?

Thus, a decider solves a decision problem if and only if it is a decider for its
corresponding language.

7 / 18

Encoding of Input

The input and output for a Turing Machine is always a string.

For any object, O, 〈O〉 will denote encoding of the object as a string.

If we have several objects, O1, . . . ,On, we denote their encoding into a single string by
〈O1, . . . ,On〉 .

8 / 18

Testing Emptiness of Regular Languages

Decision Problem:
Input: a Finite Automaton
Question: Does it define the empty language?

Language:
FA-Empty := {〈A〉 : A is a FA and L(A) = ∅}

Theorem.
FA-Empty is decidable.

9 / 18

Testing Emptiness of Regular Languages

Theorem.
FA-Empty is decidable.

Proof. (outline)

Algorithm:

Input: 〈A〉 where A is a Finite Automaton.
1. Mark the Start State of A.

2. Repeat until no new states get marked:
I Mark any state that has a transition coming into it from any state that is already

marked.
I If no final state is marked, Accept; otherwise Reject.

10 / 18

Testing Equivalence of Regular Expressions

Decision Problem:

REGULAR EXPRESSION EQUIVALENCE
Input: two Regular Expressions
Question: Do they define the same language?

For a Regular expression R, let L(R) be the language defined by R.

Language:

RegExpEquiv := {〈A,B〉 : A,B are regular expressions and L(A) = L(B)}

Theorem.
RegExpEquiv is decidable.

11 / 18

Testing Equivalence of Regular Expressions

Proof.
Algorithm:

Input: 〈A,B〉 where A and B are regular expressions
1. Construct a FA, C , that defines the language

(L(A) ∩ L(B)) ∪ (L(A) ∩ L(B)).

2. Run the previous Turing Machine, T , on C .

3. If T accepts C , then Accept, else Reject.

12 / 18

Testing Emptiness of Context Free Language

Decision Problem:

Input: a Context Free Grammar
Question: Does it define the empty language?

Language:

CFG-Empty := {G : G is a CFG and G defines the empty language}

Theorem.
CFG-Empty is decidable.

13 / 18

Testing Emptiness of Context Free Language

Algorithm:

Input: 〈A〉 where A is a Context Free Grammar.
1. Mark all the terminal symbols in A.

2. Repeat until no new symbols get marked:
I Mark any non-terminal X that has a production which has all the right-hand

symbols marked.
I If Start Symbol is not marked, Accept, else Reject.

14 / 18

Some Decidable Problems
Input: a Finite Automaton
Question: Does it define the empty language?

Input: two Regular Expressions
Question: Do they define the same language?

Input: a Finite Automaton
Question: Does it define an infinite language?

Input: a Context Free Grammar
Question: Does it define the empty language?

Input: a Context Free Grammar
Question: Does it generate an infinite language?

Input: a Context Free Grammar and a string w
Question: Can w be generated by the grammar? 15 / 18

Language classes

Decidable

CFLs

regular
languages

?

16 / 18

Closure properties

If L is decidable, then L is decidable.
If L1 and L2 are decidable, then so are

I L1 ∪ L2
I L1 ∩ L2
I L1L2
I . . .

Exercise:
Formulate and prove more closure results.

17 / 18

Revision

I Decidable Problems, decidable languages, and the link between them.

I Decision problems, relationship with languages

I Examples of Decidable Problems.

I Closure properties

Reading: Sipser, Section 4.1, pp. 190–201.

Preparation: Sipser, Section 4.2, pp. 201–213, especially pp. 207–209.

18 / 18