# Study Notes on Regular and Context Free Languages

By BYJU'S Exam Prep

Updated on: September 25th, 2023

• 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

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