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:

$L = a^* \cup a^*bc \cup a^* bb cc \cup \dots \cup a^* b^5 c^5$

(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.

It’s context-free because you can make a push-down automaton (a PDA) that accepts the $j > k$ strings and you can make a PDA that accepts the $k \not= m$ strings, and then union those two PDA’s together.
We can prove it’s not regular by using the pumping lemma. If $L$ is regular then it has a pumping length, call it $p$ . Let $s = a^{p+1} b^p c^p$ . Now break $s$ into three chunks $xyz = s$ (that’s concatenation) such that $|xy| \leq p$ , $|y| > 0$ . It should be possible that $x y^0 z$ is in the language, but in fact it’s guaranteed that $x y^0 z \notin L$ . (I thinks so, check the details yourself.) Hence, $L$ cannot be regular.