# Study Notes on Regular and Context Free Languages

By Mukesh Kumar|Updated : October 8th, 2021
• 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 be regular.

Regular Languages

1. {w |  {a, b }* }
2. {aw | w  {a, b }* }
3. {bw | w  {a, b }* }
4. {wa | w  {a, b }* }
5. {awb | w  {a, b }* }
6. {w1abw2 | w1,w2  {a, b }* }
7. { ambn | m,n>0 }
8. { ambnck | m,n,k>=0}
9. {a2n | n>=0}
Non-Regular Languages
1. { anbn | 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. {an | n is prime}
Deterministic CFLs (DCFLs)
1. { anbn | n is a positive integer }
2. {w | w has an equal number of a’s and b’s}
3. { ambn | m < n}
4. { ambn | m = 2n}
5. { ambnck | if m is even, then n=k}
6. {wCwR  | w ∈ {a, b }* , C is a special symbol and wR is the reverse of string w}
CFL’s (NCFL’s)
1. {wwR  | w  {a, b }* , and wR is the reverse of string w}
2. { ambnck | m=n or n=k}
3. { ambnck | if m=n, then n=k}
4. All regulars
5. All DCFLs
Non-CFL’s
1. { ww  | w  {a, b }*}
2. { anbncn | n>=0}
3. {an | n is prime}
4. { ambnck | m<n<k}
Important Properties:
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