1
$\begingroup$

Does the Context Free Language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$? Does $t$ fix $n$? I think the string belongs to this language.

$\endgroup$
1
  • 1
    $\begingroup$ Why do you think so? What is the specific issue/question/doubt yoiu are having? $\endgroup$
    – Raphael
    Jan 31 '16 at 11:05
4
$\begingroup$

$t$ and $n$ are independent numbers. Any string in the language consists of $t$ units, where each unit consists of $n$ $1$s followed by $n$ $2$s. In particular, then, the string generated by any choice of $t$ and $n$ contains $tn$ $1$s and $tn$ $0$s.

$\endgroup$
3
  • $\begingroup$ FWIW, unwary authors sometimes intend that the copies of $n$ are independent as well (which is a pain to denote formally). We have, of course, no way of knowing what the OP resp. their source intend, and you answer the literal question aptly. $\endgroup$
    – Raphael
    Jan 31 '16 at 11:07
  • 3
    $\begingroup$ @Raphael This is a bit like question: "What's a cat?" answer: "It's an animal that says miaow" comment: "Some people use the word 'cat' to refer to dogs." Well, great. Those people are objectively completely wrong. This isn't a valid alternative reading and I think that adding a comment drawing attention to this mistake (which I, personally, have never come across) just causes confusion. We know that either the OP's source intends what I said or is wrong. $\endgroup$ Jan 31 '16 at 16:53
  • $\begingroup$ @DavidRicherby Agreed. "We know that either the OP's source intends what I said or is wrong", if for no other reason than every string in the language is determined by a single pair $(n,t)$. Every now and then one of my students gets this wrong, as did the OP. $\endgroup$ Jan 31 '16 at 18:35
1
$\begingroup$

The way language is defined 121122 is not an acceptable string. 1212 or 11221122 is acceptable string.

The string 121122 belongs to another similar language $L_1$ where $L = \{1^n2^n\ |\ n \geq 0 \}$, $L_1 = L^*$. This might be the source of confusion.

$\endgroup$
2
  • 1
    $\begingroup$ Your $L_1$ is not the language from the question. I don't know what purpose it serves; there are uncountably-infinitely many languages that contain this given string. $\endgroup$
    – Raphael
    Feb 1 '16 at 15:26
  • $\begingroup$ I don't disagree, I was just pointing to what I thought was the source of confusion $\endgroup$
    – Shreesh
    Feb 4 '16 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.