Home, RSS feed

Models of Computation | Lecture Notes 8

2016 October 05. Wednesday.

What is this?

Fall 2016, University of Kentucky, Models of Computation, CS 575, with Dr Judy Goldsmith. These incomplete lecture notes are just my own, not proofread or endorsed by Dr G or UKY.

Guess the complexity of a language

Example 1

Consider the language $L = \{ a^i b^j c^j : 0 \leq i, 0 \leq j \leq 5 \}$. Is it regular, not regular but context-free, or not even context-free? (Remember that regular languages are a proper subset of context-free languages which are a proper subset of all formal languages.)

This is a finite union of simpler languages:

(Each of those is a regular expression.) A finite union of regular languages is regular, $L$ is regular and hence also context-free.

Example 2

Let $L = \{ a^j b^k c^m : j > k \textrm{ or } k \not= m \}$. Is it regular, only context-free, or neither?

Turns out that $L$ is context-free only.

CFL’s closed under intersection?

Let $L = \{ a^n b^n c^n : n \geq 0 \}$. This is not context-free.

Let $L_1 = \{ a^n b^n c^k : n, k \geq 0 \}$. This is context-free.

Let $L_2 = \{ a^n b^k c^k : n, k \geq 0 \}$. This is also context-free.

And $L_1 \cap L_2 = L$, so context free languages are not closed under intersection.

And for free we also get the languages are not closed under complement because

Union is a regular operation and intersection is not, so complement is not a regular operation.

And that’s lecture.

Public Domain Dedication.