COMP 598  Assignment 2

COMP 598 
Assignment 2

Question 1[10 points] Show that the language
F = {a
i
b
j
c
k
|i, j, k ≥ 0 and if i = 1 then j = k}
is not regular. Show, however, that it satisfies the statement of the pumping lemma as I proved it
in class, i.e. there is a p such that all three conditions for the pumping lemma are met. Explain
why this does not contradict the pumping lemma.
Question 2[10 points] Are the following statements true or false? Prove your answer in each case.
We have some fixed alphabet Σ with at least two letters. In the following A and B stand for
languages, i.e. subsets of Σ∗
.
• If A is regular and A ⊆ B then B must be regular.
• If A and AB are both regular then B must be regular.
• If {Ai
|i ∈ N} is an infinite family of regular sets then [∞
i=1
Ai
is regular.
• If A is not regular it cannot have a regular subset.
Question 3[10 points] If L is a language over an alphabet with strictly more than one letter we
define CY C(L) = {uv|u, v ∈ Σ
∗
, vu ∈ L}. Show that if L is regular then CY C(L) is also regular;[7].
Give an example of a non-regular language such that CY C(L) is regular. [3]
Question 4[10 points] Last week I incorrectly stated that the relation
x ≡L y ⇐⇒ ∀z ∈ Σ
∗
, xz ∈ L ⇐⇒ yz ∈ L,
defined for any language L is a congruence relation. Recall that a congruence relation ∼ is one for
which
x ∼ y, u ∼ v ⇒ xu ∼ yv.
However, Rahul pointed out that this is false. Give a counter-example showing that ≡L is not a
congruence. The correct definition that I should have given is the following
x ≈L y ⇐⇒ ∀u, v ∈ Σ
∗
, uxv ∈ L ⇐⇒ uyv ∈ L.
1
Show that ≈L is indeed a congruence relation. The quotient of Σ∗ by ≈L is called the syntactic
monoid of L. The relation ≡L is correctly defined for the Myhill-Nerode theorem; it is only the
claim that it is a congruence relation that is false.
Question 5[10 points] Which of the following pairs of formulas are equivalent? If they are not
equivalent, give a transition system which shows that the formulas have different interpretations.
If they are equivalent give a proof of the equivalence based on the semantics of the temporal
operators.
1. ✷✸φ ⇒ ✷✸ψ and ✷(φ ⇒ ✸ψ).
2. ✸(φ ∧ ψ) and ✸φ ∧ ✸ψ.
3. ✸φ and ✸ φ.
In the next two questions we will compare the expressive power of LTL and a version of fixed-point
logic adapted to paths.
Consider the following syntax for LTL:
φ ::== P|φ1 ∧ φ2|¬φ| φ|✸φ|✷φ|φ1Uφ2
where P is a set of atomic propositions. The semantics is – as usual – defined in terms of infinite
execution paths and the temporal operators have their usual meanings. We can enrich the language
by introducing fixed point operators to get the logic µ-LTL below
φ ::== P|X|φ1 ∧ φ2|¬φ| φ|µX.φ(X)|νX.φ(X)
where X stands for a variable that ranges over formulas and µ and ν are least and greatest fixedpoint operators respectively. The semantics of µ and ν are given in terms of fixed points as we
defined in class.
With the fixed point operators present we do not need any of the LTL operators except . For
example, we can write ✷φ ≡ νX.φ ∧ X. We can then use negation to get ✸.
Question 6[10 points]
1. Show how to write a formula in µ-LTL that allows one to say that a path has the property
that p (which is some fixed proposition) holds in the first state and every alternate state after
that; we call this formula odd(p). Note, I am not saying that p does not hold in any of the
other states. Thus, your formula must be satisfied by paths like: (pq)∞ as well as paths like
pqpqpppppqpqpp . . . or p∞. Here we are overloading the symbol p to stand for the state where
only p (the proposition) is true.
2. What would happen if you used the other fixed-point operator in your formula?
3. Explain why the formula p ∧ ✷(p ⇒ ¬p) ∧ ✷(¬p ⇒ p) does not express odd(p).
Question 7[10 points]
Let σi = p
i
(¬p)p∞ stand for a path where p is true for the first i steps then it is false for one state
then p is true forever. Prove: given a proposition p and any LTL (not µ-LTL) formula φ containing
n next operators, the formula φ has the same truth value on every σi with i n.
2
Now show that odd(p) cannot be expressed in LTL.
Question 8[10 points] Which of the following identities hold for ω-regular expressions?
1. (E1 + E2) · F
ω ≡ E1 · F
ω + E2 · F
ω
2. E · (F1 + F2)
ω ≡ E · F
ω
1 + E · F
ω
2
3. (E∗
· F)
ω ≡ E∗
· F
ω
.
Either prove they are equal or give a counterexample.
Question 9[10 points] Consider the processes
s0
a
~
a
??
t0
a
??
s3 s1
b
??
t1
b
??
s2 t2
Write a formula of Hennessy-Milner logic that distinguishes the states t0 and s0.
The negation-free fragment of Hennessy-Milner logic is
φ ::== true|φ1 ∧ φ2|φ1 ∨ φ2|haiφ
where a is an action. Show that the states t0 and s0 agree on all the formulas of the negation-free
fragment. This should be done by induction on the structure of formulas.
Question 10[10 points]
Let Σ = {A, B}. Construct an NBA that accepts the set of infinite words σ over Σ that start with
A and such that A occurs infinitely often in σ and between any two consecutive A’s there are an
odd number of B’s.
3