Difference between revisions of "Closure Property of Language Families"

(Created page with "Closure property is a helping to know what will be the resulting language when we do an operation on two languages of the same class. That is, suppose L_1 and L_2 belong to CF...")
 
 
(24 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
Closure property is a helping to know what will be the resulting language when we do an operation on two languages of the same class. That is, suppose L_1 and L_2 belong to CFL and if CFL is closed under operation U, then L_1 U L_2 will be CFL. But if CFL is not closed under \intersection, that doesn't mean L_1 \intersect L_2 won't be CFL. For a class to be closed under an operation, it should hold true for all languages in that class. So, if a class is not closed we cannot say anything about the result of the operation, it may or may not belong to that class. In short, closure property is useful, only when a language is closed under an operation.
+
Closure property is a helping technique to know the class of the resulting language when we do an operation on two languages of the same class. That is, suppose <math>L_1</math> and <math>L_2</math> belong to CFL and if CFL is closed under operation <math>\cup</math>, then <math>L_1 \cup L_2</math> will be a CFL. But if CFL is not closed under <math>\cap</math>, that doesn't mean <math>L_1 \cap L_2</math> won't be a CFL. For a class to be closed under an operation, it should hold true for all languages in that class. So, if a class is not closed under an operation, we cannot say anything about the class of the resulting language of the operation - it may or may not belong to the class of the operand languages. In short, '''closure property is applicable, only when a language is closed under an operation'''.
  
−
Now, while applying closure property do remember the language hierarchy. Regular \subset \subset \DCFL \subset \CFL \subset REC \subset \RE. So, if CFL is closed under Union, and L_1 and L_2 belong to CFL,  then L_1 U L_2 will be CFL. But  L_1 U L_2 may also be regular, which closure property can't tell.
+
Now, while applying closure property do remember the language hierarchy.  
 +
 +
Regular <math>\subset</math> DCFL <math>\subset</math>CFL <math>\subset</math> REC <math>\subset</math> RE.  
 +
 
 +
So, if CFL is closed under Union, and <math>L_1</math> and <math>L_2</math> belong to CFL,  then <math>L_1\cup L_2</math> will be a CFL. But  '''<math>L_1 \cup L_2</math> can also be a regular language, which closure property can't tell'''. For this we need to see <math>L_1</math> and <math>L_2</math>.
 +
 
 +
{{alert|Please don't by heart this table. This is just to check your understanding and some of them are not required for GATE|alert-danger}}
  
 
:{| class="wikitable"
 
:{| class="wikitable"
−
|+ align="top"|Closure properties of language families (<math>L_1</math> Op <math>L_2</math> where both <math>L_1</math> and <math>L_2</math> are in the language family given by the column). After Hopcroft and Ullman.
+
|+ align="top"|Closure properties of language families
 
|-
 
|-
 
! Operation
 
! Operation
−
!
 
 
! Regular
 
! Regular
−
! [[Deterministic context-free language|DCFL]]
+
! DCFL
−
! [[Context free language|CFL]]
+
! CFL
−
! [[Indexed language|IND]]
+
! CSL
−
! [[Context sensitive language|CSL]]
+
! Recursive
−
! [[Recursive language|recursive]]
+
! RE
−
! [[Recursively enumerable language|RE]]
 
 
|-
 
|-
−
|[[Union (set theory)|Union]]
+
|Union
−
| <math>\{w | w \in L_1 \lor w \in L_2\} </math>
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 26: Line 28:
 
| {{Yes}}
 
| {{Yes}}
 
|-
 
|-
−
|[[Intersection (set theory)|Intersection]]
+
|Intersection
−
| <math>\{w | w \in L_1 \land w \in L_2\}</math>
 
 
| {{Yes}}
 
| {{Yes}}
−
| {{No}}
 
 
| {{No}}
 
| {{No}}
 
| {{No}}
 
| {{No}}
Line 36: Line 36:
 
| {{Yes}}
 
| {{Yes}}
 
|-
 
|-
−
|[[Complement (set theory)|Complement]]
+
|Complement
−
| <math>\{w | w \not\in L_1\}</math>
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
−
| {{No}}
 
 
| {{No}}
 
| {{No}}
 
| {{Yes}}
 
| {{Yes}}
Line 46: Line 44:
 
| {{No}}
 
| {{No}}
 
|-
 
|-
−
|[[Concatenation]]
+
|Concatenation
−
| <math>L_1\cdot L_2 = \{w\cdot z | w \in L_1 \land z \in L_2\}</math>
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 57: Line 53:
 
|-
 
|-
 
|Kleene star
 
|Kleene star
−
| <math>L_1^{*} = \{\epsilon\} \cup \{w \cdot z | w \in L_1 \land z \in L_1^{*}\}</math>
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 67: Line 61:
 
|-
 
|-
 
|Homomorphism
 
|Homomorphism
−
|
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
Line 76: Line 68:
 
| {{Yes}}
 
| {{Yes}}
 
|-
 
|-
−
|e-free Homomorphism
+
|<math>\epsilon</math>-free Homomorphism
−
|
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 86: Line 76:
 
| {{Yes}}
 
| {{Yes}}
 
|-
 
|-
−
|Substitution
+
|Substitution (<math>\epsilon</math>-free)
−
|
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 97: Line 85:
 
|-
 
|-
 
|Inverse Homomorphism
 
|Inverse Homomorphism
−
|
 
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 107: Line 93:
 
|-
 
|-
 
|Reverse
 
|Reverse
−
| <math>\{w^R | w \in L\} </math>
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{No}}
 
| {{No}}
−
| {{Yes}}
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 116: Line 100:
 
| {{Yes}}
 
| {{Yes}}
 
|-
 
|-
−
|Intersection with a [[regular language]]
+
|Intersection with a regular language
−
| <math>\{w | w \in L_1 \land w \in R\}, R \text{ regular}</math>
 
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
Line 124: Line 107:
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
 
| {{Yes}}
−
| {{Yes}}
+
 
−
<!--
 
−
|-
 
−
|Min
 
−
|
 
−
| {{Yes}}
 
−
| {{Yes}}
 
−
| {{No}}
 
−
| {{?}}
 
−
| {{Yes}}
 
−
| {{Yes}}
 
−
| {{Yes}}
 
−
|-
 
−
|Max
 
−
|
 
−
| {{Yes}}
 
−
| {{Yes}}
 
−
| {{No}}
 
−
| {{?}}
 
−
| {{No}}
 
−
| {{No}}
 
−
| {{No}}
 
−
|-
 
−
|Init
 
−
|
 
−
| {{Yes}}
 
−
| {{No}}
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{No}}
 
−
| {{No}}
 
−
| {{Yes}}
 
−
|-
 
−
|Cycle
 
−
|
 
−
| {{Yes}}
 
−
| {{No}}
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{Yes}}
 
−
| {{Yes}}
 
−
| {{Yes}}
 
−
|-
 
−
|Shuffle
 
−
|
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{Yes}}
 
−
|-
 
−
|Perfect Shuffle
 
−
|
 
−
| {{Yes}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{?}}
 
−
| {{Yes}}
 
−
-->
 
 
|}
 
|}
  
Line 197: Line 118:
 
{{Template:FBD}}
 
{{Template:FBD}}
  
−
[[Category: Automata Theory]]
+
[[Category: Automata Theory Notes]]
  
−
[[Category:Notes & Ebooks for GATE Preparation]]
 
  
 
[[Category: Compact Notes for Reference of Understanding]]
 
[[Category: Compact Notes for Reference of Understanding]]

Latest revision as of 20:51, 7 December 2015

Closure property is a helping technique to know the class of the resulting language when we do an operation on two languages of the same class. That is, suppose <math>L_1</math> and <math>L_2</math> belong to CFL and if CFL is closed under operation <math>\cup</math>, then <math>L_1 \cup L_2</math> will be a CFL. But if CFL is not closed under <math>\cap</math>, that doesn't mean <math>L_1 \cap L_2</math> won't be a CFL. For a class to be closed under an operation, it should hold true for all languages in that class. So, if a class is not closed under an operation, we cannot say anything about the class of the resulting language of the operation - it may or may not belong to the class of the operand languages. In short, closure property is applicable, only when a language is closed under an operation.

Now, while applying closure property do remember the language hierarchy.

Regular <math>\subset</math> DCFL <math>\subset</math>CFL <math>\subset</math> REC <math>\subset</math> RE.

So, if CFL is closed under Union, and <math>L_1</math> and <math>L_2</math> belong to CFL, then <math>L_1\cup L_2</math> will be a CFL. But <math>L_1 \cup L_2</math> can also be a regular language, which closure property can't tell. For this we need to see <math>L_1</math> and <math>L_2</math>.

Heads Up! Please don't by heart this table. This is just to check your understanding and some of them are not required for GATE
Closure properties of language families
Operation Regular DCFL CFL CSL Recursive RE
Union Yes No Yes Yes Yes Yes
Intersection Yes No No Yes Yes Yes
Complement Yes Yes No Yes Yes No
Concatenation Yes No Yes Yes Yes Yes
Kleene star Yes No Yes Yes Yes Yes
Homomorphism Yes No Yes No No Yes
<math>\epsilon</math>-free Homomorphism Yes No Yes Yes Yes Yes
Substitution (<math>\epsilon</math>-free) Yes No Yes Yes No Yes
Inverse Homomorphism Yes Yes Yes Yes Yes Yes
Reverse Yes No Yes Yes Yes Yes
Intersection with a regular language Yes Yes Yes Yes Yes Yes







blog comments powered by Disqus
Retrieved from "https://gatecse.in/w/index.php?title=Closure_Property_of_Language_Families&oldid=5607"

Closure property is a helping to know what will be the resulting language when we do an operation on two languages of the same class. That is, suppose L_1 and L_2 belong to CFL and if CFL is closed under operation U, then L_1 U L_2 will be CFL. But if CFL is not closed under \intersection, that doesn't mean L_1 \intersect L_2 won't be CFL. For a class to be closed under an operation, it should hold true for all languages in that class. So, if a class is not closed we cannot say anything about the result of the operation, it may or may not belong to that class. In short, closure property is useful, only when a language is closed under an operation.

Now, while applying closure property do remember the language hierarchy. Regular \subset \subset \DCFL \subset \CFL \subset REC \subset \RE. So, if CFL is closed under Union, and L_1 and L_2 belong to CFL, then L_1 U L_2 will be CFL. But L_1 U L_2 may also be regular, which closure property can't tell.

Closure properties of language families (<math>L_1</math> Op <math>L_2</math> where both <math>L_1</math> and <math>L_2</math> are in the language family given by the column). After Hopcroft and Ullman.
Operation Regular DCFL CFL IND CSL recursive RE
Union w \in L_1 \lor w \in L_2\} </math> Yes No Yes Yes Yes Yes Yes
Intersection w \in L_1 \land w \in L_2\}</math> Yes No No No Yes Yes Yes
Complement w \not\in L_1\}</math> Yes Yes No No Yes Yes No
Concatenation w \in L_1 \land z \in L_2\}</math> Yes No Yes Yes Yes Yes Yes
Kleene star w \in L_1 \land z \in L_1^{*}\}</math> Yes No Yes Yes Yes Yes Yes
Homomorphism Yes No Yes Yes No No Yes
e-free Homomorphism Yes No Yes Yes Yes Yes Yes
Substitution Yes No Yes Yes Yes No Yes
Inverse Homomorphism Yes Yes Yes Yes Yes Yes Yes
Reverse w \in L\} </math> Yes No Yes Yes Yes Yes Yes
Intersection with a regular language w \in L_1 \land w \in R\}, R \text{ regular}</math> Yes Yes Yes Yes Yes Yes Yes







blog comments powered by Disqus