Closure Property of Language Families [Table]

This post contain some common closure properties on the families of languages corresponding to the Chomsky hierarchy, as well as other related families.

Closure Property of Language, table for Closure Property of Language , Closure Property of Language remember for GATE CSE exam

Operation REG DCFL CFL CSL RC RE
Union Y N Y Y Y Y
Intersection Y N N Y Y Y
Set Difference Y N N Y Y N
Complementation Y Y N Y Y N
Intersection with a regular language Y Y Y Y Y Y
Concatenation Y N Y Y Y Y
Kleene star Y N Y Y Y Y
Kleene plus Y N Y Y Y Y
reversal Y Y Y Y Y Y
free homomorphism Y N Y Y Y Y
homomorphism Y N Y N N Y
inverse homomorphism Y Y Y Y Y Y
free substitution Y N Y Y Y Y
substitution Y N Y N N Y

where the definitions of the cells in the top row are the following language families:

Abbreviation Name
REG Regular
DCFL Deterministic Context-free
CFL Context-free
CSL Context-sensitive
RC Recursive
RE Recursively Enumerable

Leave a Reply

Your email address will not be published. Required fields are marked *