Short Notes Regular and Context Free Languages - Theory of Computation

 Page 1


1. Every regular language is also CFL, but every CFL need not be regular.
2. Every DCFL is also CFL, but every DCFL need not be regular.
3. Every regular language is also DFCL, but every DCFL need not regular.
Regular Languages
1. {w | w e {a, b }*}
2. {aw | w e {a, b }*}
3. {bw | w e {a, b }*}
4. {wa | w e {a, b }*}
5. {awb | w e {a, b }*}
6. {w-iabw2 | w-|,w2 e {a, b }*}
7. { am bn | m,n>0 }
8. { am bn ck | m,n,k>=0}
9. {a2 n | n>=0}
Non-Regular Languages
1. { anbn | n is a positive integer}
2. { ww | w e {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}
Page 2


1. Every regular language is also CFL, but every CFL need not be regular.
2. Every DCFL is also CFL, but every DCFL need not be regular.
3. Every regular language is also DFCL, but every DCFL need not regular.
Regular Languages
1. {w | w e {a, b }*}
2. {aw | w e {a, b }*}
3. {bw | w e {a, b }*}
4. {wa | w e {a, b }*}
5. {awb | w e {a, b }*}
6. {w-iabw2 | w-|,w2 e {a, b }*}
7. { am bn | m,n>0 }
8. { am bn ck | m,n,k>=0}
9. {a2 n | n>=0}
Non-Regular Languages
1. { anbn | n is a positive integer}
2. { ww | w e {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. { am bn | m < n}
4. { am bn | m = 2n}
5. { am bn ck | if m is even, then n=k}
6. {wCwR | w e {a, b }*, C is a special symbol and wR is the reverse of string w} 
CFL’s (NCFL’s)
1. {wwR | w e {a, b }*, and wR is the reverse of string w}
2. { am bn ck | m=n or n=k}
3. { am bn ck | if m=n, then n=k}
4. All regulars
5. All DCFLs
Non-CFL’s
1. { ww | w e {a, b }*}
2. { anbn cn | n>=0}
3. {an | n is prime}
4. { am bn ck | m<n<k}
Important Properties:
1. Let L be a Context Free Languages, and R be a regular language. Then
1. L fl R = always CFL and need not be regular
2. L u 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 fl R = always DCFL and need not be regular
2. D u 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