Talk:Dyck language

From Wikipedia, the free encyclopedia

Socrates
Philosophy Portal
This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details.
??? This article has not yet received a rating on the quality scale.
??? This article has not yet received an importance rating on the importance scale.

Wouldn't it be much easier to define a Dyck language as one following the grammar:

N → [ N ] | [ ] N | N [ ] |

I think this is much more readable than the insert/delete notation. 84.58.215.217 19:12, 21 November 2006 (UTC)


Yes, it is more readable but it is not as handy for formal proofs. Nevertheless, one should present it here.

Another remark: Actually, there is more than one Dyck language, namely one for every positive integer, denoting the number of different types of brackets. 132.187.9.77 15:43, 2 April 2007 (UTC)

Ah and I think that your grammar is not correct (It cannot generate [[]][[]], for example). A better one would be perhaps

S -> SS | [S] | ε

132.187.9.77 15:47, 2 April 2007 (UTC)


I removed the following:

  • The Dyck language with two distinct types of parentheses can be recognized in the complexity class TC0.

First, no citation is given. Second, I believe the statement is incorrect. Sudborough ("On Deterministic Context-Free Languages, Multihead Automata, and the power of an auxiliary pushdown store", STOC '76: Proceedings of the eighth annual ACM symposium on Theory of computing, pp. 141-148, 1976) showed that the Dyck language on two types of parenthesis is (in some sense) complete for DCFL (the set of all languages log-space reducible to deterministic context-free languages). If Dyck_2 is solvable in TC^0, then all of DCFL = TC^0, which is not known and indeed not likely to be the case. —Preceding unsigned comment added by 129.93.165.5 (talk) 18:19, 28 March 2008 (UTC)

Ok. After checking and rechecking, it appears that the original statement was correct. I've restored it, but it still needs a citation. It should be cited to Barrington and Corbett, Information Processing Letters 32 (1989) 251-256. —Preceding unsigned comment added by 129.93.165.5 (talk) 20:53, 31 March 2008 (UTC)