[PDF] Lecture Notes 15: Closure Properties of Decidable Languages 1 PDF CS340-Theory-of-Computation-15-toc.pdf

Union Both decidable and Turing recognizable languages are closed under union - For decidable languages the proof is easy Suppose L1 and L2 are two decidable languages accepted by halting TMs M1 and M2 respectively The machine for L1 U L2 is designed as follows: Given an input x, simulate M1 on x

Decidable languages are closed under ∪, °, *, ∩, and Need to show that union of 2 decidable L's is also decidable Closure for Recognizable Languages

[PDF] Closure Properties of Decidable and Recognizable Languages

28 oct 2009 · Recognizable Languages Robb T Koether Homework Review Closure Properties of Decidable Languages Intersection Union Closure

[PDF] Lecture A,C notes - CSE 105 Theory of Computation

Closure properties (D) ○ Decidable languages are closed under – Union – Intersection – Set Complement – Set Difference – ○ Proof: similar to the

[PDF] 6045J Lecture 7: Decidability - MIT OpenCourseWare

only countably many co-Turing-recognizable languages For union, accept if either accepts decidable languages are closed under concatenation and

[PDF] Decidable and Undecidable Languages - Welcome to Wellesleys

decidable 1 we'll need to get some practice describing decidable languages Closure Properties of Dec and RE Dec is closed under: • union • intersection

[PDF] Tutorial 3

This is surely a decidable language, however, any language L is now a Prove that the class of decidable languages is closed under union, concatenation and

[PDF] 1 Closure Properties

Proposition 1 Decidable languages are closed under union, intersection, and complementation Proof Given TMs M1, M2 that decide languages L1, and L2

[PDF] CSE 6321 - Solutions to Problem Set 1

Show that the collection of decidable languages is closed under the following operations 1 complementation Solution: Proof Let L be a decidable language and M be the Turing machine that decides L (a) On input 2 intersection Solution:

[PDF] Turing decidable languages are closed under intersection Proof

Theorem: Turing decidable languages are closed under complement Proof: Let M be a TM which decides L It is easy to construct the machine schema for a TM

[PDF] union of two non regular languages

[PDF] union security insurance company medicare supplement claims mailing address

[PDF] uniontown pa warrant list 2020

[PDF] unique businesses in switzerland

[PDF] unique characteristics of ants

[PDF] unique college essays

[PDF] unique practices in singapore

[PDF] unisex joggers size chart

[PDF] unisex size chart

[PDF] unit 12 trigonometry homework 6 law of cosines answers

[PDF] unit 3: weather lesson 49 worksheet answers

[PDF] unit 6: prepositions

[PDF] unit a1 lecturers close bolton

[PDF] unit of magnetic flux

[PDF] unit of magnetization

CS340: Theory of ComputationSem I 2017-18

Lecture Notes 15: Closure Properties of Decidable Languages

Raghunath TewariIIT KanpurWe will study the closure properties of decidable and Turing recognizable languages under some

of the standard operations on languages.

1 Closure Properties of Decidable and Turing Recognizable

Languages

1.Union

Both decidable and Turing recognizable languages are closed under union. F ordecidable languages the pro ofis easy .Supp oseL1andL2are two decidable languages accepted by halting TMsM1andM2respectively. The machine forL1[L2 is designed as follows: Given an inputx, simulateM1onx. IfM1accepts thenaccept, else simulateM2onx.

IfM2accepts thenacceptelsereject.

No wsupp oseL1andL2are two Turing recognizable languages accepted by TMsM1 andM2respectively. SinceL1andL2are Turing recognizable languages, therefore for strings that do not belong to these languages, the corresponding machines may not even halt. The previous strategy will not work because we can have a scenario where M

2acceptsxbutM1loops forever.

Here the trick is to simulate bothM1andM2\simultaneously". In other words, we design a machine that executes one step ofM1, followed by one step ofM2, then again one step ofM1and so on.

2.Concatenation

Both decidable and Turing recognizable languages are closed under concatenation. I will give the proof for Turing recognizable languages. The proof for decidable languages is similar. LetL1andL2be two Turing recognizable languages. Given an inputw, use nondeterminism and guess a partitionw(sayw=xy). Now run the respective Turing machines ofL1andL2onxandyrespectively. If both accepts thenacceptelsereject.

3.Star

Both decidable and Turing recognizable languages are closed under star operation. This is also similar to concatenation. Nondeterministically rst guess a numberk, and then guess akpartition of the given input. Now for each string in the partition, check whether it belongs to the original language.

4.Intersection

Both decidable and Turing recognizable languages are closed under intersection. Run the TMs of both the languages on the given input.acceptif and only if both the machines accept. In the case of intersection we can run the TMs ofL1andL2one after the other (as opposed to union).

5.Complementation

Decidable languages are closed under complemen tation.T odesign a mac hinef orthe complement of a languageL, we can simulate the machine forLon an input. If it accepts thenacceptand vice versa. T uringrecognizable languages are not closed und ercomplemen t.In fact, Theorem 1 better explains the situation. Theorem 1.A languageLis decidable if and only if bothLandLare Turing recognizable. Proof.IfLis decidable then it is Turing recognizable. Moreover since decidable languages are closed under complement,Lis also Turing recognizable. SupposeLis Turing recognizable via a TMMandLis Turing recognizable via a TMM0. Given an inputx, simulatexon both the machinesMandM0simultaneously (similar to union). IfM accepts thenacceptand ifM0accepts thenreject. Observe that since the stringxeither belongs toLorLtherefore one of the two machines must acceptx.quotesdbs_dbs17.pdfusesText_23

[PDF] [PDF] Lecture Notes 15: Closure Properties of Decidable Languages 1