Discrete Structures

Discrete Structures 1. et language A = { w | w can be written as ajbk where k is a multiple of j.}.

a. (7) Show that A is not regular.

2. Let language B = { w | w can be written as c#d#cR#e with c, d, e ∈ {a, b}* }. a. (7) Show that B is not regular.

b. (8) Show that B is context-free.

3. Let C be the language over {a, b, c, d, e, f} accepting all strings so that:

1. There are precisely two b’s in the string.

2. Every a is immediately followed by an odd number of e’s.

3. Every d is immediately followed by an even number of f’s.

4. 4. e’s and f’s don’t occur except as provided in rules 2 and 3.

5. All a’s occur after the first b.

6. All d’s occur before the second b.

7. In between the two b’s there are exactly twice as many a’s as d’s.

HINT: Don’t be intimidated by the number of rules. The way they interact actually helps you

simplify the number of cases you have to deal with while constructing this grammar.

a. (20) Construct a context-free grammar generating C. Explain how your construction accounts for each rule.

b. (5) We could eliminate one rule from C and make it regular. Which rule would that be, and why would it

work? You do not need a formal proof, but you do need an explanation.

4. A homomorphism on an alphabet is a function that gives a string for each symbol in that alphabet – for example, a

homomorphism h on the binary alphabet might be defined so that h(0) = ba and h(1) = edc.

Homomorphisms can be extended to strings and languages in the straightforward way:

• If s = s1s2s3…sn then h(s) = h(s1) h(s2) h(s3)… h(sn).

• If L is a language then h(L) = { h(s) | s is in L }.

Show that the class of context free languages is closed under homomorphism – that is, that for any context

free language L, and any homomorphism h on its alphabet, h(L) defined as above is context free.

HINT: If your proof is very long, you are doing more than you need to.

5 Let G = (V, ∑, R, S) be a grammar with V = {Q, R, T}; ∑ = {q, r,ts}; and the set of rules:

S → Q

Q → q | RqT

R → r | rT | QQr | 𝜀

T → t | S| tT

a. (20) Convert G to Chomsky Normal Form.

b. (5) Convert the language of G to a PDA.