Peter Linz Edition 4 Exercise 7.1 Question 3.c,3.d,4.f,4.j (Page No. 183)

Question

Q3) Given,

$L_1 = (aaa^*b)$

$L_2 = (aab^*aba^*)$

Find (c) the union of $L_1$ and $L_2$, and also find (d) $L_1 - L_2$.

Q4) Find the npda's of the following:

f)  $L = \{ a^nb^m :n \leq m \leq 3n\}$

j) $L = \{w  : 2n_a(w) \leq n_b(w)) \leq 3n_a(w) \}$.

Comments

L1 union  L2= aaa*b+aab*aba*....

L1-L2= aa(ϵ + aaa*)b = aab + aaaaa*b

Answer 1

L1 U L2 Will be
aaa*b*aba*

L1 - L2 will be aaaaa*b + aab

Q2
1 is DPDA
2 is NPDA