Impotant properties in Theory of computation

Regular and Context Free Languages

• Every regular language is also CFL, but every CFL need not be regular.
• Every DCFL is also CFL, but every DCFL need not be regular.
• Every regular language is also DFCL, but every DCFL need not regular.

Regular Languages

• {w | w ∈ {a, b }^* }
• {aw | w ∈ {a, b }^* }
• {bw | w ∈ {a, b }^* }
• {wa | w ∈ {a, b }^* }
• {awb | w ∈ {a, b }^* }
• {w₁abw₂ | w₁,w₂ ∈ {a, b }^* }
• { a^mbⁿ | m,n>0 }
• { a^mbⁿc^k | m,n,k>=0}
• {a²ⁿ | n>=0}

Non-Regular Languages

• { aⁿbⁿ | n is a positive integer }
• { ww | w ∈ {a, b }^* }
• {w | w has an equal number of a’s and b’s}
• {w| w is a palindrome of a’s and b’s}
• {aⁿ | n is prime}

Deterministic CFLs (DCFLs)

• { aⁿbⁿ | n is a positive integer }
• {w | w has an equal number of a’s and b’s}
• { a^mbⁿ | m < n}
• { a^mbⁿ | m = 2n}
• { a^mbⁿc^k | if m is even, then n=k}
• {wCw^R  | w ∈ {a, b }^* , C is a special symbol and w^R is the reverse of string w}

CFL’s (NCFL’s)

• {ww^R  | w ∈ {a, b }^* , and w^R is the reverse of string w}
• { a^mbⁿc^k | m=n or n=k}
• { a^mbⁿc^k | if m=n, then n=k}
• All regulars
• All DCFLs
• 
  

Non-CFL’s

• { ww  | w ∈ {a, b }^*}
• { aⁿbⁿcⁿ | n>=0}
• {aⁿ | n is prime}
• { a^mbⁿc^k | m<n<k}

Important Properties:

• Let L be a Context Free Languages, and R be a regular language. Then
  • L ∩ R = always CFL and need not be regular
  • L ∪ R = always CFL and need not be regular
  • L – R  = always CFL and need not be regular
  • R – L = Always CSL but need not be CFL
• Let D be a DCFL, and R be a regular language. Then
  • D ∩ R = always DCFL and need not be regular
  • D ∪ R = always DCFL and need not be regular
  • D – R  = always DCFL and need not be regular
  • R – D = Always DCFL but need not be regular