1. Let L={ab, aa, baa}. Which of the following strings are in L*: abaabaaabaa, aaaabaaaa, baaaaabaaaab, baaaaabaa ? Which strings are in L4 ?
Solution:
The strings present in L* are :
abaabaaabaa ( The partitioning can be done as: ab aa baa ab aa)
aaaabaaaa (The partitioning can be done as: aa aa baa aa)
baaaaabaa (The partitioning can be done as: baa aa ab aa)
The strings present in L4 are:
aaaabaaaa (The partitioning can be done as: aa aa baa aa)
baaaaabaa (The partitioning can be done as: baa aa ab aa)
2. Find grammars for ∑ ={ a,b }, that generate the sets of
a) All strings with exactly one a.
b) All strings with at least one a.
c) All strings with no more than three a's.
d) All strings with at least three a's.
Solution:
a) The grammar for exactly one a is
G= ({S}, {a, b}, S, P)
where P: S->BaB
B-> bB | λ
b) The grammar with at least one a is
G=({S}, {a, b}, S, P)
where P: S-> BaB
B-> bB| aB | λ
c) The grammar with no more than three a's is :
G= ({S}, {a, b}, S, P)
where
P: S-> SaS| AaA| λ
A-> AbA | BaB| λ
B-> BbB| CaC| λ
C->CbC| λ
d) The grammar with at least three a's is:
G=({S},{a, b}, S, P)
where
P: S-> BaBaBaB
B-> abB| aB | bB | λ
3. For ∑ ={ a,b }, construct dfa's that accept the sets consisting of
a) all strings with exactly one a.
Solution:
b) all strings with at least one a.
Solution:
c) all strings with no more than 3 a's
Solution:
d) all strings with at least one a and exactly two b's.
Solution:
e) all strings with exactly two a's and more than two b's.
Solution:
0 Comments