Study Notes on Regular and Context Free Languages

By Mukesh Kumar|Updated : July 31st, 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

Important Links

GATE CSE Question Papers

GATE CSE Study Plan

GATE CSE Exam Analysis

GATE Study Material for CSE

GATE CSE Exam Pattern 2022, Sectional timing, Marking Scheme

ISRO EC Question Papers

GATE CSE Syllabus 2022

ISRO EC Study Plan

ISRO EC Syllabus

Thanks

Prep Smart. Score Better!

Download BYJU'S Exam Prep app for Exam Preparation here

Posted by:

Mukesh KumarMukesh KumarMember since Feb 2020
Share this article   |

Comments

write a comment
Load Previous Comments
Dhannjay Sharma
{ ambnck | if m=n, then n=k}
@Mallesham Devasane sir ..
Is this CFL ??
abhijit sen

abhijit senSep 21, 2016

R-L how come it's a CSL..
Mukul Dilwaria
Discuss more questions on toc and compiler at https://gatestack.in/c/theory-of-computation-and-compiler
Somoshree Datta
Please refer to this site for explanation:
https://gateoverflow.in/30669/identify-whether-language-context-free-context-sensitive
SAMEER TRIMADE
Howcome R-L is a CSL lang.
Rakesh Nama

Rakesh NamaOct 15, 2019

TOC handwritten notes Taken from rabindra babu ravula's online video lecture...
Pages from Theory of computation.pdf
Preeti Kumari
Please active the notes of Turing machine.

Follow us for latest updates