Automata and Formal Languages
Assignment 4
Due: 5/1
1) Find NFA’s that accept the following languages:
a) L((a + b)a * ) ∩ L(baa * )
b) L(ab*a * ) ∩ L(a *b*a )
2) The symmetric difference of two sets S1 and S2 is defined as:
S1θ S2 = {x : x ∈ S1 or x ∈ S2 but x is not in both S1 and S2}.
Show that the family of regular languages is closed under symmetric difference.
3) If L is a regular language, prove that the language {uv : u ∈ L, v ∈ LR } is also regular.
4) The head of a language is the set of all prefixes of its strings, that is,
head ( L) = { x : xy ∈ L for some y ∈ Σ*}
Show that the family of regular languages is closed under this operation.
5) For a string a1a2 ...an define the operation shift as:
shift ( a1a2 ...an ) = a2 ...an a1
From this we can define the operation on a language as
shift ( L) = {v : v = shift ( w) for some w ∈ L} .
Show that regularity is preserved under the shift operation.
6) Determine whether or not the language L = {w : na ( w) = nb ( w)} is regular?
How about L* ?
7) Prove that the following languages are not regular:
a) L = {a n bl a k : k ≥ n + l}
b) L = {a n bl a k : n = l or l ≠ k}
c) L = {a n bl : n ≤ l}
d) L = {ww : w ∈ {a , b}*}
© Copyright 2025 ExpyDoc
