Consider the alphabet Σ = {0,1}. The reversal of a string is the string consisting of the symbols of the string in rever

[answerhappygod]

1 (34.09 KiB) Viewed 39 times

Consider the alphabet Σ = {0,1}. The reversal of a string is the string consisting of the symbols of the string in reverse order. The reversal of the string w is denoted by w (i) Find the reversal of the following bit strings: (a) 0101 (b) 1 1011 (c) 1000 1001 0111 (ii) Give a recursive definition of the reversal of a string. [Hint: First define the reversal of the empty string A. Then write a string w of length n+1 as zy, where is a string of length n, and express the reversal of w in terms of TR and y.] x (iii) Use structural induction to prove that (w₁w₂) = wwf for two words w₁ and ₂.