[deprosun]

Let Σ be the alphabet {a, b}, let X be the language Σ*a, and let Y be the language bΣ*.
How many strings of length exactly four are in the language XYX?
a. None
b. Sixteen
c. Four
d. Three

My approach:
Since its XYX, and we need exactly 4, X cannot be the length more than 2 because there are two X's and Y has a minimum of length 1. So I am coming to the conclusion that only Y can length two and X's will have length one. So this is my observation:
- X will only be the string "a"
- Y will either be "bb" or "ba". It cannot be more than length 2.

So abba, and abaa are only two strings possible according to me. But I dont have an option for that .

What do you guys think?

This post has been edited by deprosun: 17 September 2013 - 07:34 AM

[sepp2k]

XYX means "a word from the language X, followed by a word from the language Y, followed by a word from the language X". It does not mean that the first word from language X and the second word from language X need to be the same. So something like this would be in the language:

X  Y X
aa b a

This post has been edited by sepp2k: 17 September 2013 - 07:51 AM

[deprosun]

That makes all the sense!

[deprosun]

Seems like there are only 4 then:
baba
aaba
abba
abaa

Correct?

[sepp2k]

Yes, that's correct.