For any string x, define x^R to be that same string reversed. The intuition is p
ID: 3405701 • Letter: F
Question
For any string x, define x^R to be that same string reversed. The intuition is plain enough, but to support proofs we'll need a formal definition: epsilon^R = epsilon (ax)^R = x^R a, for any symbol a and string x We'll use the same notation to denote the set formed by reversing every string in a language: A^R = {x^R I x Element A} Using these definitions, prove the following properties of reversal: Prove that for any strings x and y, (xy)^R = y^Rx^R. Prove that for any string xy (x^R)^R = x. Prove that for any languages A and B, (A Union B)^R = A^R Union B^R.Explanation / Answer
a)Inductive Step: Assume that (xy)r = yrxr holds for an arbitrary string y. --- Induction Hypothesis
We are going to show that (x(ya))r = (ya) rxr holds for any symbol a in .
(x(ya))r = ((xy)a)r by the associativity of concatenation
= a(xy)r by the definition of reversal
= a(yrxr) by the induction hypothesis.
= (ayr)xr by the associativity of concatenation
= (ya)rxr by the definition of reversal
Thus (xy)r = yrxr for any strings x and y.
b)Induction hypothesis: if 0 |x| n, then (x R) R = x. Induction step: Suppose |w| = n + 1. Then we can write w = xa, where a is a symbol and 0 |x| n.
Then (w R) R = ((xa) R) R since w = xa = (axR) R since (xy) R = y Rx R (use inner R and think of a as a string of length 1) = (x R) Ra R same as previous line but using outer R = (x R)a = xa = w since w = xa (by the induction hypothesis).
3)For a string x=x1x2…xn, xR =xn…x2x1,For a language A, AR= {xR | x A},Show that if A is regular, so is A.
Proof.
(1) R= is regular.
(2) For any symbol a, {a}R = {a} is regular.
(3) Suppose that for regular languages A and B, AR and BR are regular. Then
(A U B)R = AR U BR is regular,
(AB)R = BR AR is regular.
(A*)R = (AR )* is regular.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.