Recursion with strings

Question

Let $A$ be a set of strings on the alphabet ${a, b}$ starting with $a$ and ending with $b$ and they don't have occurrences of $ba$ as a substring. For example, $abab ̸∉ A$, $ab ∈ A$, $abb ∈ A$, $aabab ̸∉ A$, $aaab ∈ A$.

(i) Provide a recursive definition of A.

My attempt:

Base: $λ∈A$ (empty string)

Recursive Passage: ?

Please exaplin me how to do it.

Recognize that they are all of the form (several a's)(several b's)., e.g. aaabb, or aabbbb, or abbbbbb. The only question is how many $a$'s and how many $b$'s there are. Note further, the emptystring does not satisfy the condition that it begins with $a$... the smallest string in your set is the string $ab$. — JMoravitz, Jun 11 '18 at 16:55
As for coming up with a recursive definition... again, $ab$ is the smallest string in the collection. Any other string can be formed by adding some $a$'s to the beginning or adding some $b$'s to the end. — JMoravitz, Jun 11 '18 at 16:56

score 1 · Answer 1 · answered Jun 11 '18 at 16:59

1

The empty string is not in $A$, since any element of $A$ must start with $a$, and end with $b$.

A recursive specification for $A$ can be given as follows . . .

$ab\in A$.$\\[4pt]$
If $x\in A$, then $ax\in A$, and $xb\in A$.

answered Jun 11 '18 at 16:59

quasi

58,772

What is the string x? – user565089 Jun 11 '18 at 17:02
An arbitrary element of $A$. – quasi Jun 11 '18 at 17:03
But if the arbitrary element is $a$ then $ax$ is not correct... ? – user565089 Jun 11 '18 at 17:05
But $a$ is not an element of $A$. It's recursive; to apply the rule, $x$ must already be an element of $A$. – quasi Jun 11 '18 at 17:07
The elements of A are a and b, x is either a or b – user565089 Jun 11 '18 at 17:53
No, the elements of the alphabet are the symbols $a$ and $b$. By the specified rules, neither of the strings $a$ or $b$ is in $A$. – quasi Jun 11 '18 at 17:59
Let us continue this discussion in chat. – user565089 Jun 11 '18 at 18:12

score 1 · Answer 2 · answered Jun 11 '18 at 17:02

1

Recursive definition of A:

$ A := ab | aA | Ab $

answered Jun 11 '18 at 17:02

Angel Moreno

844

score 0 · Answer 3 · answered Jun 11 '18 at 17:08

Since the strings have to start with $a$ and end with $b$, your base case isn't the empty string but $ab$. From there, your options are to add an $a$ or a $b$. If you add a character to a 2-character string, there are three places to put it: a the beginning, middle, or end. If you add an $a$ to $ab$, the beginning and middle are the same, and the end is not allowed, since that will create an instance of $ba$. Thus, you can consider the beginning to be the only place to put an $a$. Similarly, the only place to put a $b$ is at the end. This means that you end up with a string of $a$'s and $b$'s, with all of the $a$'s before the $b$'s. Every time you add an $a$, you can have to add it to the beginning (otherwise you would create an instance of $ba$), and every time you add a $b$, you have to add it to the end. So $A =\{ab, aS, Sb: S \in A\}$

Recursion with strings

3 Answers3