1. Assume the following facts. Let be an alphabet. (a) For all strings w , w = w
ID: 667865 • Letter: 1
Question
1. Assume the following facts. Let be an alphabet. (a) For all strings w , w = w = w. ( is the identity element for string concatenation.) (b) For all strings w , w 0 = . (c) For all strings w and integers n 0, w n+1 = w nw. (d) For all strings u , v , and w , u(vw) = (uv)w. (Associativity of concatenation.) (e) || = 0. (f) For all strings w and symbols a , |wa| = |w| + 1. (g) R = . (h) For all strings w and symbols a , (wa) R = awR. (i) Basic properties of integer arithmetic such as associativity and commutativity of addition and multiplication, identity elements for addition (i.e., 0) and multiplication (i.e., 1), and distribution of multiplication over addition.
Prove (uv) R = v Ru R for all strings u and v . Give justifications for each of your steps (e.g., facts from the above list).
Explanation / Answer
consider (uv)R.
Case 1: if v= , i.e |v|=0
(uv)R =(u)R
= (u)R by (h)
= uR
=R uR by (g)
=vR u R since, v=
Case 2: if u =
(uv)R =(v)R
= vR
=(v)R by (h)
= (vR) by (a)
=(vR) by (a)
= R vR by (g)
= uR vR since, u=
Case 3: if v = a , a
(uv)R =(ua)R
= a (u)R by (h)
=auR
=aR uR by (g)
=vR u R since, v=
Case 4: if u = a, a
(uv)R =(av)R
=vRa by (h)
=vRaR since, reverse of a symbol is same as the symbol
=vRuR since, u=
Case 5: if v= abcd…yz, where a,b,c,…z a
Consider v= wz, where w= abc…y
(uv)R = (uwz)R
=((uw)z)R by (d)
=z(uw)R by (h)
Again consider w= sy, where s= abcd…x
= z(usy)R
=z((us)y)R by (d)
=zy(us)R by(h)
And so on.
=zyx….cba(u )R
= zyx….cba(u)R
= vR uR, Since, v=abc…xyz and vR = zyx…cba
Hence (uv)R=vR uR
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.