Question

1(a)Draw the state diagram for a DFA for accepting the following language over
alphabet {0,1}:
{w | the length of w is at least 2 and has the same symbol in its 2nd and last
positions}

(b)Draw the state diagram for an NFA for accepting the following language over
alphabet {0,1} (Use as few states as possible):
{w | w is of the form 1*(01 ∪ 10*)*}

(c)If A is a language with alphabet Σ, the complement of A is the set of all strings over
Σ that are not in A.
Show, with the help of a diagram, that the class of regular languages is closed
under complement. That is, show that if A is a regular language, then so is the
complement of A.

(d)Prove that the following language, A, is NOT regular, by using the Pumping
Lemma for regular languages.
A ={ab^nc^n | n≥ 0}.

Thank you very much.

Answer 1

answer of que 1

answer of que 2

que3

Let M = < Q , , q0 , , x > be a DFA that accepts a language L. Then a DFA that accepts the complement of L, i.e. * - L, can be obtained by swapping its accepting states with its non-accepting states, that is Mc = < Q , , q0 , , Q - x > is a DFA that accepts * - L .

For example the following DFA accepts the language a+ over = { a , b }.

ques 4

Let L = {ab^nc^n | n ≥ 1}.
Then L is not regular.
Proof: Let n be as in Pumping Lemma.
Let w = ab^nc^n
If L is a regular language, then there is an integer n > 0 with the property that: (*) for any string x ∈ L where |x| ≥ n, there are strings u, v, w such that

(i) x = uvw, (ii) v != null (iii) |uv| ≤ n, (iv) uvkw ∈ L

for all k ∈ N. To prove that a language L is not regular, we use proof by contradiction.

Here are the steps. 1. Suppose that L is regular.

2. Since L is regular, we apply the Pumping Lemma and assert the existence of a number n > 0 that satisfies the property (*).

3. Give a particular string x such that (a) x ∈ L, (b) |x| ≥ n. This the trickiest part. A wrong choice here will make step 4 impossible.

4. By Pumping Lemma, there are strings u, v, w such that (i)-(iv) hold. Pick a particular number k ∈ N and argue that uvkw != L, thus yielding our desired contradiction.

Let L = {ab^kc^k : k ∈ N}. We prove that L is not regular.

[step 1] By way of contradiction, suppose L is regular.

[step 2] Let n be as in the Pumping Lemma.

[step 3] Let x = ab^nc^n . Then x ∈ L [definition of L] and |x| = 2n ≥ n.

[step 4] By Pumping Lemma, there are strings u, v, w such that

(i) x = uvw, (ii) v !=null, (iii) |uv| ≤ n, (iv) uvkw ∈ L for all k ∈ N.

Let y be the prefix of x with length n. I.e., y is the first n symbols of x. By our choice of x, y = ab^n .

By (i) and (iii), uv = ab^j for some j ∈ N with 0 ≤ j ≤ n.

Combining with (ii), v = 0^j for some j ∈ N with 0 < j ≤ n.

By (iv), uv^2w ∈ L.

(#) Aside: We are picking k = 2. Indeed, any k != 1 will do here.

However, uv^2w = uvvw = ab^n+jc^n is not belonging to L,

[definition of L; since j > 0, n + j != n] which contradicts (#). Therefore L is not regular.