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.
On
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\}$
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 . . .