I am taking an undergraduate CS Theory course and the material on finite automata and regular languages is being taught in a non-traditional manner. Instead of using regular expressions, the closure properties of regular languages, the pumping lemma etc, to show that a language is or is not regular, all of our proofs and examples for identifying regular languages use the Myhill-Nerode theorem and boolean matrices as defined below.

Let $L = \{w_1, w_2, ...\}$ be a set of words over some alphabet $\Sigma$ and let $T_L$ be a matrix with entries $t_{ij}$ where

$$ t_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{if } w_iw_j \in L \\ 0 & \mbox{otherwise} \end{array} \right. $$

Then by Myhill-Nerode, L is non-regular iff all rows of $T_L$ are distinct.

Correction: Then by Myhill-Nerode, $L$ is non-regular iff $T_L$ has an infinite number of distinct rows.

My question is, are there any readily available books, papers, or lecture notes that lean heavily on this technique and are appropriate for undergrads?

  • havent seen this. if its not in any undergraduate book [of which there are very many], its probably not really appropriate for undergradates.... isnt this a question for the teacher? what does s/he say? – vzn Oct 26 '13 at 16:44
  • here is another case where matrix algebra is used to analyze # of words in a regular language, wonder if there is some natural connection... – vzn Oct 26 '13 at 19:50
  • The professor admits that there are few resources tailored to undergrads that use this approach. Which is fine, it just puts a premium on taking detailed notes during lectures. – Sean Grossman Oct 26 '13 at 19:56
  • sean, actually somewhat disagree. part of undergraduate education is focus on well-established, basic principles of the field that are well-documented in textbooks (and elsewhere eg internet). this appears to be a very advanced approach. are the students all at advanced level? the Myhill-Nerode theorem is for finding minimal FSMs, have not heard of it used for determining regularity.... also, saw this question on tcs.se for awhile, does anyone know, was it migrated? imho think it might be more appropriate on tcs.se.... – vzn Oct 26 '13 at 20:32

I wanted to make this a comment, but it is too long.

First, your definition of the matrix is poorly written and probably wrong. There is no reason to introduce indices $i, j$. My guess is that the right definition is the following: $T$ is the infinite matrix $(T_{u,v})_{u, v \in A^*}$ defined by $$ T_{u,v} = \begin{cases} 1 &\text{if $uv \in L$}\\ 0 &\text{otherwise} \end{cases} $$ Next, your claim

$L$ is non-regular if and only if all rows of $T$ are distinct

is wrong. Take $A = \{a, b\}$ and $L = \{ u \in A^* \mid |u|_a = |u|_b\}^1$. Then $T_{1,v} = T_{ab,v}$ for all $v \in A^*$, so the rows $T_{1, -}$ and $T_{ab,-}$ are equal although $L$ is not regular. What is true however is that $L$ is regular if and only if $T$ has finitely many distinct rows.
${}_{\text{(1) $|u|_c$ denotes the number of occurrences of the letter $c$ in $u$.}}$

References. The matrix $T$ is used in the larger setting of noncommutative formal power series under the name of Hankel matrix. Here is a good reference, but I am afraid it is not really appropriate for undergraduate students.

[1] J. Berstel and C. Reutenauer, Noncommutative rational series with applications. Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0

  • can the Hankel matrix indeed be used to strictly determine language regularity? – vzn Oct 26 '13 at 16:41
  • @vzn Yes, as I said, a language is regular if and only if its Hankel matrix has finitely many distinct rows. There is an analogous result for noncommutaitve power series: a series is rational iff its Hankel matrix has finite rank (you need the notion of rank in this case). – J.-E. Pin Oct 26 '13 at 18:36
  • ok. there are many, many questions related to proving language regularity on cs.se presumably for undergraduate classes where the std method is the pumping lemma... to your knowledge can this work in general for undergraduate-type exercises? your response seems to support that maybe its rarely to never used at the undergraduate level.... – vzn Oct 26 '13 at 19:46
  • @vzn To be honest, I was wondering in which context does an undergraduate CS theory course introduce Hankel matrices as a tool for teaching regular languages. This is a nice theory, but not an easy one, in my opinion. – J.-E. Pin Oct 26 '13 at 20:03
  • I've corrected the claim to read "L is non-regular iff the matrix has an infinite number of distinct rows." My apologies for the confusion. – Sean Grossman Oct 26 '13 at 20:05

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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