Maybe someone can shine some light on this problem:
When given the Language L which is defined as:
L := {w ϵ {a,b}* : w=(aba | ba | (ba | w')), with w' ϵ L}
What kind of word can this Language create? Especially if looking at w'.
Does the w' mean that it can be replaced with aba or ba or can it only be replaced with the ba's that are inside of the (ba | w') part?
Smallest words are obviously aba and ba but once I get to the w' part, I am not sure what it can do there.
To be clear, my first intuition would be that the w' can recursively write/read ba's and aba's BUT apparently (when going by a GIVEN solution) it should only allow babababa and so on... Why not abaaba...?
The production
w=(aba | ba | (ba | w'))
can be expanded to the following choices:
With these production rules, there can be no infinite recursion.
If there were no pipe symbol between ba and w', then you could build infinitely long chains of repeated ba. Note, though, that even then, such a long word could never start with an a, as the production that creates aba does not allow for any repetition afterward.