Practice Prelim #2

P 326 : 47
(b)
	F{3,4},{2,5},S{1,6}
	/* F- final state ; S- start state */

(c)
	SF{0,1},{2,5},{3,6}, inac{4}

P 328 : 52 (i)
(a)
	SF{1,2},{4,5},{3,7}, inac{6}

(b)
	SF{1,2},{3,5},{6,7}, inac{4}

P 334: 72
(a)
	L = {a^n b^2n c^k | n, k >= 1}
A CNF grammar for L:
S -> QC
Q -> AR | AD
A -> a
R -> QD
D -> BB
B -> b
C -> CC | c

A GNF grammar for L:
S -> aQBBC
Q -> aQBB | aBB
A -> a
B -> b
C -> c | cC

We generate as many c's as needed, then for every a generated there are two
b's.

(c)
	L = {a^k b^m c^n | 2k >= n and m, n, k >= 1}

A CNF grammar for L:
S -> QC
B -> b | BB
Q -> RS
R -> AB
B -> BB | b
A -> a
C -> c | DD
D -> c

A GNF grammar:
S -> aSC | bB | b
B -> bB | b
C -> c | cD
D -> c

Every time an a is produced, either one c or two c's are produced. So there
are at most twice as many c's as a's.


P 336 : 84
(a)
	{a^n b^m c^k | 2n = 3k or 5k = 7m}

Context-free. We give a grammar for the subset where 2n = 3k, and another
grammar for the subset where 5k = 7m. Union the two in the normal way and
get a grammar for the whole language.

2n = 3k:
S_1 -> aaa S_1 cc | aaaBcc
B -> bB | b

We produce as many b's as we want, while twice the number of a's = thrice
the number of c's. (Note this means the number of a's is a multiple of 3 and
the number of c's is a multiple of 2, because these numbers must be
integral, while 2 and 3 are relatively prime.)

5k = 7m:
S_2 -> AQ
Q -> bbbbbQccccccc | bbbbbccccccc
A -> aA | a

Same basic reasoning.

(c)
	L={a^n b^m c^k | n,m ,k >=1 and (n != 3m  or n != 5k) }

	let L1={a^n b^m c^k | n,m ,k >=1 and n != 3m }
	    L2={a^n b^m c^k | n,m ,k >=1 and n != 5k }

	a CFG for L1 is
		S1-> S2 C 
		S2-> aaa S3 b | aB | aaB  
		S3-> aaa S3 b | A | aB | aaB
		A-> aA | a
		B-> BB | B
		C-> cC | c
	
	a CFG for L2 is
		S4-> aaaaa S5 c | aBC | aaBC | aaaBC | aaaaBC 
		S5-> aaaaa S5 c | AB | aBC | aaBC | aaaBC | aaaaBC

	therefore CFG for L is
		S -> S1 | S4
(e)
	L={a^n b^m c^k | n,m,k >=1 ; n+m=k}
	L is a CFL.

	L={a^n b^n b^k c^k | n, k >=1}

	S->S1 S2
	S1->a S1 b | ab
	S2->b S2 c | bc


P 336 : 85

(c) { x | x is a power of 2 in binary }
     This language is regular; it can be described by the regular
     expression
            1 0*

(d) L(a*b*c*)
     Regular expression can describe only a regular language;
     it's regular.


(e) Language L of words consisting of balanced parentheses
     of three types (, ), [, ], {, }

     First we show that L is not regular. If we take a homomorphism h
     that maps [, ], { and } to epsilon and leaves ( and ) unchanged,
     we get h(L) = PAREN1 is the language of balanced parentheses,
     which is known to be context free and not regular. (An alternate
     proof that L is not regular would involve the pumping lemma).

     Next, we show a CF grammar for L and conclude that L is context free:

     S -> (S)  |  [S]  | {S}  |  SS  |  epsilon

(f) not regular
    proof using myhill nerode theorem : 
	a^i & a^j where i < j belong to distinct equivalence
	classes because a^i b^j is in L but a^j b^j is not in L.
    	hence a, aa , aaa , .... all belong to distinct equivalences and
	clearly the number of number of equivalence classes is not finite
	& therefore not regular.

    is a CFL
	S->aSa | aA | bB
	A->aA | e	("e" is the empty string)
	B->bB | e

(k) not regular
    proof using myhill nerode theorem : 
	a^i & a^j where i < j belong to distinct equivalence
	classes because a^i b^i is not in L but a^j b^i is in L.
    	hence a, aa , aaa , .... all belong to distinct equivalences and
	clearly the number of number of equivalence classes is not finite
	& therefore not regular.
	
    not a CFL
    proof using pumping lemma :
	let "k" be the constant of the pumping lemma. then 
	z=a^(k+2) b^(k+1) c^k is in L & length > k. therefore we
	can write z=uvwxy for some u,v,w,x & y. it should be obvious that
	v consists of either only a's or only b's or only c's. so too x.
	suppose v is not the empty string : if v consists of only a's
	then uwy is not in the language because either #(b's) >= #(a's) or
	#(c's) >= #(b's) which is a contradiction . next case, if
	v consists of only b's , then we can pump up the # of b's & the
	pumped up string is not in the language because #(b's) > #(a's).
	similarly if v consists of only c's.
	the same reasoning is applied if v is empty but x is non empty.  
	

(l) not regular
    proof using myhill nerode theorem : 
	a^i & a^j where i < j belong to distinct equivalence
	classes because a^i b^i c^i is not in L but a^j b^i c^i is in L.
    	hence a, aa , aaa , .... all belong to distinct equivalences and
	clearly the number of number of equivalence classes is not finite
	& therefore not regular.

    is a CFL
	S->S1 | S2

	S1->S3 C 
	S3->a S3 b | a A
	A-> a A | e		
	C->c C | e	

	S2-> A S4
	S4->b S4 c | b B
	A-> a A | e		
	
Hopcroft-Ulmann P 143 : 6.17
a.) accepted


S,A,C
B       B
S,A,C   S,A,C   S,A,C   
B       B       B       B
A,C     A,C     A,C     A,C     A,C     
-----------------------------------
a       a       a       a       a


b.) Not Accepted

B
S,A,C   S,A,C
B       B       B
S,A,C   S,A,C   S,A,C   S,A,C
B       B       B       B       B
A,C     A,C     A,C     A,C     A,C     A,C
-------------------------------------------
a       a       a       a       a       a