Automata Theory (Theory of Computation)

<Closure Property>

• Regular Language is closed under union, intersection, concatenation, star, and complement

• Context Free Language is closed under union, concatenation, and star. But, it is NOT closed under intersection and complement.

• Decidable Language is closed under union, intersection, concatenation, star, and complement.

• Recognizable Language is closed under union, intersection, concatenation, and star. But, it is NOT closed under complement.

<Decidability>

• All finite languages are decidable 

• Only infinite language can be undecidable.

• There are many infinite languages that are decidable (Σ* is infinite but decidable)

<Some Facts>

• Every finite language is always regular language.

• Every subset of a countable set is either countable or finite.

<Decidable language vs Recognizable language>

• Decidable language is also known as Recursive language. Turing machine will always halt for decidable languages. It will accept and halt if it is in the language and reject (= halt) strings if it is not in the language.

• Recognizable language is also known as Recursively enumerable language. Turing machine will halt sometimes & may not halt sometimes. It will accept and halt if it is in the language. It will either reject (= halt) or not halt if it is not in the language.