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