Given $m,n\in\mathbb{N}$, finite alphabet $A=\{a,b,c\}$, and $L=\{(a^m,a^n)\}^*=\{(a^{mk},a^{nk})|k∈N\}\subseteq A^*\times A^*$. Is this binary language $L$ regular over $A(2,\$)$ (i.e. $\{A∪\{\$\}\}\times \{A∪\{\$\}\}\setminus \{\$,\$\}$)?

For example, is this binary language $L=\{(a^3,a^7)\}^*=\{(a^{3k},a^{7k})|k∈N\}=\{(a^3,a^7),(a^6,a^{14}),(a^{9},a^{21})(a^{12},a^{28})...\}$ regular over $A(2,\$)$?

An illustration of the difference between binary regular language and unitary regular language: Let $L=\{(w,w')\mid w\in L^1,w'\in L^2\text{, and }L^1,L^2\text{ are unitary languages}\}$ be a binary language, the length of $w$ and $w'$ maybe not all the same (suppose some $|w|>|w'|$). Firstly, we must add \$'s behind $w'$ such that all $|w|=|w'\$...|$, then we get a new language $L^{\$}$. And we will say $L$ is regular if and only if $L^{\$}$ is regular (i.e. there is exist a finite binary automaton to recognize $L^{\$}$).

And if the binary language $L$ can be showed as finite regular binary languages with the operations: union, intersection, complement, concatenation, $L$ is also regular.

  • $\begingroup$ I tried to fix the formatting to make the question more comprehensible, but it is not clear what you are asking and what the role of the whole second part of the question is. Consider rephrasing. $\endgroup$ – Dave Clarke Jun 26 '13 at 7:14
  • $\begingroup$ My question : Is the binary language $L=\{(a^m,a^n)\}^*=\{(a^{mk},a^{nk})| k∈N\}$ regular over $A(2,\$)$ ? And I know it's "Yes" when $m=n$ ,but I don't know the case $m≠n$. Thesecond part is just a illustration of the difference between binary regular language and unitary regular language . $\endgroup$ – John Jun 26 '13 at 9:56
  • 3
    $\begingroup$ Can you modify your question to reflect this fact? And be careful with placing punctuation and spaces. $\endgroup$ – Dave Clarke Jun 26 '13 at 10:05
  • $\begingroup$ But the binary language is definted like this ,maybe I shall write it in Hendrik Jan's way. $\endgroup$ – John Jun 26 '13 at 13:33
  • $\begingroup$ The point is that the question is not as comprehensible as it could be. Just listing some facts does not convey the relationship between those facts. It's a matter of communication. $\endgroup$ – Dave Clarke Jun 26 '13 at 13:40

If I understand your question, you should consider $(a,aa)^* = \{ ( a^n, a^{2n} ) \mid n\ge 0 \}$.

Perhaps the following notation helps $(a,aa)^* = \{ \left(\begin{array}{c}a^n\\ a^{2n} \end{array}\right)\mid n\ge 0\}$. Interpreted over a two level alphabet this should be interpreted as $\{ \left(\begin{array}{c}a\\ a\end{array}\right)^n \left(\begin{array}{c}\$\\ a\end{array}\right)^n \mid n\ge 0\}$.

Your turn to conclude.

Here I assume \$'s can only be added at the end of the string.

  • $\begingroup$ Yes,it's a special case.And I know this binary language is regular over $A(2,\$)$ when $m=n$,but I don't know the case $m≠n$. $\endgroup$ – John Jun 26 '13 at 9:45
  • 2
    $\begingroup$ My example has $m=1$ and $n=2$. Look what happens there. $\endgroup$ – Hendrik Jan Jun 26 '13 at 9:54
  • $\begingroup$ Yes,I know.Can you do it ? $\endgroup$ – John Jun 26 '13 at 9:58
  • $\begingroup$ :Yes,you are right. Maybe I shall write it in your way. $\endgroup$ – John Jun 26 '13 at 13:35

If I have understood your notion of "binary language" (which is unfortunately not defined in the question), it appears that your question (in the special case $m=3,n=7$) is isomorphic to the following:

Is the language $K^\$ = \{b^{3k} c^{4k} : k \in \mathbb{N}\}$ regular over the alphabet $\{b,c\}$?

The answer to that question is "No". To see why, see the relevant reference questions here: Reference answers to frequently asked questions and How to prove that a language is not regular?.

Explanation: The isomorphism is as follows: $b=(a,a)$ and $c=(\$,a)$. In other words, when you have the pair $(a,a)$ in the binary language, we can map this to a new symbol $b$ (in an ordinary, "unitary" language); when you have $(\$,a)$ in the binary language, we can map it to a new symbol $c$; and when we have $(a,\$)$, we can map it to a new symbol $d$. Now all words in the binary language $L^\$$ are a concatenation of some sequence of $(a,a)$, $(\$,a)$, and $(a,\$)$, so we can map them to a word over the alphabet $\{b,c,d\}$.

Or, to put it another way: if I've understood the definition of a binary language correctly (which I might not have), you can think of the language $L^\$$ as a binary language, or you can alternatively think of it as an ordinary, "unitary" language over the alphabet $\{(a,a), (\$,a), (a,\$)\}$.

When $m=3,n=7$, applying the above isomorphism to $L^\$$ yields the language $K^\$$ I defined above. Now standard methods suffice to determine whether $K^\$$ is regular; indeed, for $m=3,n=7$, it is not regular.

The general question: You should be able to use similar techniques to answer your question for all $m,n$, on your own.

Background on the site: To give you a little bit of further explanation about this site: The expectation on this site is that you will work out the details of those on yourself. If your question can be answered using the techniques described there, then it is most likely not a good fit for this site. This site's primary purpose is to create an archive of content that will be useful for others. Also, we expect people to do some research/work on their own first before asking here. If the question can be answered using standard techniques (for proving that a language is not regular), then the question is not likely to be a good fit for this site, because it is likely too localized to be of use to others and because it does not meet the requirement for self-effort.

If this is not what you were asking, you'll need to edit the question to be more clear about what you are asking and to define all terms. You should also edit the question to show what you have tried so far.

  • $\begingroup$ No,please read my question carefully. The above $L$ is subset of $A^*\times A^*$,not $A^*$.(The ∗ operator is the Kleene star) $\endgroup$ – John Jun 28 '13 at 4:46
  • $\begingroup$ @John, I did read your question carefully. I believe my answer does answer your question. You said that $L$ (the binary language) is defined to be regular if and only if $L^\$$ (a language that is a subset of $A^*$) is regular. In my answer, I showed that $L^\$$ is not regular. Consequently, $L$ is not regular either. If this is a misunderstanding, I hope you can explain exactly what the misunderstanding was and edit the question to make your question clearer -- because I did make an honest effort to read your question carefully. $\endgroup$ – D.W. Jun 28 '13 at 5:28
  • $\begingroup$ When $m=3,n=7$, $L^\$=\{(a^{3k}\$^{4k},a^{7k})|k∈N\}$,not $\{a^{3k}\$^{4k}a^{7k}:k∈N\}$. It is binary language ,not unitary language. $\endgroup$ – John Jun 28 '13 at 6:15
  • $\begingroup$ @John, OK, then I have indeed misunderstood the question. So, then, what is the definition of a binary language, and what does it mean to say that a binary language is regular? (what is the definition of "regular" in the context of a binary language?) I've not seen this concept in my students before. $\endgroup$ – D.W. Jun 28 '13 at 6:21
  • 1
    $\begingroup$ OK, @John, I've edited the answer to reflect my latest guess at what you mean by a binary language. (Strictly speaking, I shouldn't have to guess... but maybe you can now check whether this answer is what you were looking for.) $\endgroup$ – D.W. Jun 28 '13 at 6:32

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.