0
$\begingroup$

Consider the recursively defined language, $L_2$

i) $x \cap L_2$ and $y \in L_2$
ii) if $w \in L_2$, then so is $wxw \in L_2$

Find all strings in L_2 with length less than $7$ characters (note: $w$ is a meta symbol)

I am a bit confused—does this mean that $x$ and $y$ are the only two "words" in language $L_2$?

For instance:

Strings with length of two: $xy, yx, xx, yy$

Strings with length of three: $xxx, yyy, xyy, xyx, xxy, yxx, yxy, yyx$

and so on up to 7 strings? The $x$ intersect $L_2$ is throwing me off a bit.

$\endgroup$
2
  • $\begingroup$ I think that "The x intersect L2" is a typo for $x \in L_2$ ... $\endgroup$ Commented May 9, 2015 at 21:39
  • $\begingroup$ and if that was the case than I would be correct in my answer. I will ask. thanks. $\endgroup$ Commented May 9, 2015 at 21:45

1 Answer 1

0
$\begingroup$

Like Mauro, I think that the intersection symbol is a typo, and that the base clause is that $x\in L_2$ and $y\in L_2$. I also assume that the asterisk in (ii) merely indicates that $w$ is a meta symbol and is not itself a symbol of the language. Thus, every word of $L_2$ that is not $x$ or $y$ can be decomposed into three parts: a word $w\in L_2$, an $x$, and a second copy of $w$. This means that $L_2$ has no words of length $2$, and its words of length $3$ are $xxx$ and $yxy$. Does it have any other words of length less than $7$?

$\endgroup$
2
  • $\begingroup$ thank you...i didnt notice my error. $\endgroup$ Commented May 9, 2015 at 22:01
  • $\begingroup$ @Ducksauce88: You’re welcome. $\endgroup$ Commented May 9, 2015 at 22:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .