The recursive definition given below defines a set S of stri

The recursive definition given below defines a set S of strings over the alphabet {a, b}: Base case: lambda S and a S Recursive rule: if x S then, xb S (Rule 1) xba S (Rule 2) Use structural induction to prove that if a string x S, then x does not have two or more consecutive a\'s. Use strong induction on the length of a string x to show that if x does not have two or more consecutive a\'s, then x S Specifically, prove the following statement parameterized by n: For any n greaterthanorequalto 0, let x be a string of length n over the alphabet {a, b} that does not have two or more consecutive a\'s, then x S.

Solution

Structural induction is a more convenient form of induction it used instead of mathematical induction to prove a result about a recursively defined sets.

a)S is defined over the set {a,b}

S contains strings that is a and b

Here base case is belongs to S

Means a E s

Recursive rule:

Xb E S

Xba E S

Using structural induction if x is belongs to the S as pre the base rule s contains both a and b

And as per the recursive rule xb belongs to S

                                                      Xba belongs to S

Let x be a new element constructed in the recursive

If the first term of the sequence which is built by the set S is suppose a and the second is derived from the first [from the recursive law]

Xb belongs to s   there fore x belongs to s and x belongs to x

Xba belongs to S there fore x belongs to s and {a,b} belongs to S

So [xb][xba] belongs to S

As per the recursive rule the next term is depend on the previous term.

Xbaa belongs to s

So x does not have the consecutive a’s

b) in the sequencing problems we use strong induction

By using strong induction from the above we are clear with x is no consecutive of a’s

The length of the string assume n where n>= 0

Let x be a string form the set of S so x belongs to S, n is the length of the string in x.

The strings are derived from the set S {a,b}

In the sequence first term is xb,xba,xbab,xbaba….so on

In the give sequence there is no consecutive a’s followed .