Talk:Dyck language

This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.PhilosophyWikipedia:WikiProject PhilosophyTemplate:WikiProject PhilosophyPhilosophy articles

Low

This article has been rated as Low-importance on the project's importance scale.

Associated task forces:
/
	Logic

Mathematics Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Low	This article has been rated as Low-priority on the project's priority scale.

Better definition

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)[reply]

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)[reply]

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)[reply]

I think that the grammar form it's more readable and prone to be used for learning purposes. We shall keep both forms, thus to give to poor students like me an easier way to fix the concept in their minds.

A short and correct Grammar should be the following:

S → ( S ) S | ε

I disagree with 132.187.9.77 that the context free grammar is less handy for formal proofs. The context-free grammar definition is inductive, and thus admits easy structural induction. If one were to formalize proofs about the Dyck language in, for example, Coq, it would be easiest with the CFG. 72.70.58.29 (talk) 18:55, 14 August 2017 (UTC)[reply]

Recognition in complexity class TC⁰

I removed the following:

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

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)[reply]

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)[reply]

I am adding a reference to the aforementioned article dvberkel (talk) 05:52, 5 August 2015 (UTC)[reply]

clarifying the insert and delete functions

I do not understand the insert and delete functions. First, I feel like I need to know whether the first character of the string is in position zero or position one. Position one is more natural, but apparently since the domains of the functions include zero the reader should infer from that that the strings begin with position zero. Making this explicit or changing the definitions to first-character-is-in-position-one would be helpful. Second, while for the insert function I can decode the almost-too-brief "inserted into the jth position" into "inserted before the parenthesis in position j" (Two characters will not fit into a single position.), I am unable to decode the delete function's "'[]' deleted from the jth position". Position j holds only one parenthesis, so what does it mean to delete a pair from that position? My inclination is to interpret that as "Delete the parenthesis in position j and then find its matching parenthesis, which could be many positions away to the left or right, and delete that, too.". But that interpretation mismatches the boundary condition "delete(u, j) is undefined if j > |u| − 2". The "2" should be a "1". Any comments before I go in and start messing with the article text? IOLJeff (talk) 21:40, 10 October 2009 (UTC)[reply]

parentheses ( ) versus square brackets [ ]

Parentheses are round. The article should either continue to use square brackets and call them "square brackets" or switch to parentheses and continue to call them "parentheses". I prefer parentheses but hesitate to edit in that direction in case the literature conventionally uses square brackets. IOLJeff (talk) 21:50, 10 October 2009 (UTC)[reply]

I am changing the usage of "parentheses" to "brackets", but will drop the monicker "square" after the introduction. dvberkel (talk) 05:43, 5 August 2015 (UTC)[reply]

Missing Dyck languages with more than one type of parentheses

This article is missing most of the theory of Dyck languages. A good source is: http://planetmath.org/encyclopedia/WellBalanced.html Also, the Chomsky-Schützenberger theorem referenced is not the correct one (see the discussion of that article). And also, the Chomsky-Schützenberger is about Dyck languages with n types of parentheses for some n, not necesarilly n=2. — Preceding unsigned comment added by 201.231.234.10 (talk) 06:53, 8 September 2011 (UTC)[reply]

Better definition for n ≥ 1

The given definition using imbalance is only accurate for the Dyck language over 1 pair of brackets. If the imbalance is merely the difference between the number of opposite brackets, then you'd consider $ab{\bar {a}}{\bar {b}}$ to be a Dyck word as the overall imbalance is positive and is positive for every prefix of the word (and for each type of bracket).

A simple and quite understandable definition, I believe, is as the equivalence class of $1$ through the transitive closure of the relation $\approx$ such that $ua{\bar {a}}v\approx uv$ for each symbol $a$ and every words $u,v$ .

I think the grammar generating the Dyck language is quite simple and helps the understanding too: $D\rightarrow \epsilon +DD+aD{\bar {a}}$ as it points out that every Dyck word is obtained by concatenating two Dyck words or surrounding one with opposite brackets. — Preceding unsigned comment added by Mak4wiki (talk • contribs) 12:43, 3 October 2016 (UTC)[reply]

Really hard to read with square brackets.

Can we get a discussion on switching to parens from the current square brackets? The various example strings given look like incomprehensible vertical lines and boxes in some fonts. 72.70.58.29 (talk) 18:10, 14 August 2017 (UTC)[reply]

I totally agree. The choice of character is arbitrary, and using parentheses would substantially improve readability. 148.88.169.37 (talk) 13:29, 22 January 2018 (UTC)[reply]