Study Notes on Regular and Context Free Languages

Regular Languages

1. {w | w ∈ {a, b }^* }
2. {aw | w ∈ {a, b }^* }
3. {bw | w ∈ {a, b }^* }
4. {wa | w ∈ {a, b }^* }
5. {awb | w ∈ {a, b }^* }
6. {w₁abw₂ | w₁,w₂ ∈ {a, b }^* }
7. { a^mbⁿ | m,n>0 }
8. { a^mbⁿc^k | m,n,k>=0}
9. {a²ⁿ | n>=0}

1. { aⁿbⁿ | n is a positive integer }
2. { ww | w ∈ {a, b }^* }
3. {w | w has an equal number of a’s and b’s}
4. {w| w is a palindrome of a’s and b’s}
5. {aⁿ | n is prime}

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

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

1. { ww  | w ∈ {a, b }^*}
2. { aⁿbⁿcⁿ | n>=0}
3. {aⁿ | n is prime}
4. { a^mbⁿc^k | m<n<k}

1. Let L be a Context-Free Languages, and R be a regular language. Then
   1. L ∩ R = always CFL and need not be regular
   2. L ∪ R = always CFL and need not be regular
   3. L - R  = always CFL and need not be regular
   4. R - L = Always CSL but need not be CFL
2. Let D be a DCFL, and R be a regular language. Then
   1. D ∩ R = always DCFL and need not be regular
   2. D ∪ R = always DCFL and need not be regular
   3. D - R  = always DCFL and need not be regular
   4. R - D = Always DCFL but need not be regular

You can follow the detailed champion study plan for GATE CS 2021 from the following link:

Detailed GATE CSE 2021 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series! (100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering

Thanks

#DreamStriveSucceed