User talk:Ksbooth

EMTM enter multiple tag mode and LMTM leave multiple tag mode.

God knows why I remember these things.

Welcome!

Hello, Ksbooth, and welcome to Wikipedia! Thank you for your contributions, especially your edits to Chomsky hierarchy. I hope you like the place and decide to stay. Here are a few links to pages you might find helpful:

You may also want to complete the Wikipedia Adventure, an interactive tour that will help you learn the basics of editing Wikipedia. You can visit the Teahouse to ask questions or seek help. Need some ideas about what kind of things need doing? Try the Task Center.

Please remember to sign your messages on talk pages by typing four tildes (~~~~); this will automatically insert your username and the date. If you need help, check out Wikipedia:Questions, ask me on my talk page, or ask for help on your talk page, and a volunteer should respond shortly. Again, welcome! PetraMagna (talk) 06:58, 20 January 2024 (UTC)[reply]

Just want to welcome you and note that I fixed the issue you pointed out in Chomsky hierarchy. If you notice any other issues, please don't hesitate to let me know or fix it yourself. PetraMagna (talk) 06:59, 20 January 2024 (UTC)[reply]

Thanks. I am pseudo-new to Wikipedia. I made a few contributions some years back, but then not much for quite some time. So I am indeed still a bit of a novice. I think the EMTM and LMTM comment is from that era.

I noticed you had changed the languages to n>0 while I was editing other parts. That's a better solution, I think, rather than dealing with epsilon-rules.

There are now examples for Type-3 and Type-2, but Type-1 is a challenge. There is an example on the context-sensitive page Context-sensitive grammar#anbncn but it is a bit complicated. There are simpler grammars for the language using the equivalent definition that requires the RHS of a rule to be at least as long as the LHS but allows more than one non-terminal to be rewritten. But the definition currently used is nicer because it illustrates the hierarchy, which the alternate definition does not show as well.

I am tempted to add a link to the example rather than repeat the example verbatim, because without an explanation, the example is not that easy to understand, which sort of defeats the purpose of having an example. Ksbooth (talk) 08:11, 20 January 2024 (UTC)[reply]

I think linking to the full example is a good idea. The Chomsky hierarchy article is meant to be a summary and is already linking to other articles for more details. The only issue is that the example in Context-sensitive grammar is unsourced. You can read WP:V and WP:NOR if you are interested, but the short version is that all non-trivial statements need to be verifiable through a source. For example, I looked at the lecture PowerPoint referenced in Chomsky hierarchy, and it say n > 0 for regular languages, which is nice because I can change n ≥ 0 to n > 0 knowing that it's backed by a source. It would be great if those examples for context-sensitive grammar can be sourced, but I think you can be bold and keep doing what you are doing now regardless.

As for welcomes, I just think it's nice for people to know that their contributions are seen and appreciated. Perhaps a "welcome back" message is more appropriate here. PetraMagna (talk) 05:47, 21 January 2024 (UTC)[reply]

Non-trivial is in the eye of the beholder. :)

My textbooks are all ancient (Seymour Ginsberg's and Michael Harrison's from the 60s and 70s) and I am not sure I actually have them any more. As an instructor, I found many of the more recent textbooks managed to confuse students rather than enlighten them. The grammar is definitely correct. Changing n ≥ 0 to n > 0 is fine because there is a theorem that if L is regular L-R is regular where R could be {epsilon}, and similarly if L is CFL L-R is CFL (i.e., in these two cases, adding or deleting a finite number of strings from either language changes nothing in terms of the types of the languages). The Type-3 and Type-2 grammars really are trivial. But I get the rule.

I will see if I can find references for Type-3 and Type-2.

Type-1 is not trivial, which is why I would reference the other page. The other page has a pseudo-proof, which is not that difficult but a full proof is actually tricky. In most of these situations, proving that every string in the language can be derived from the grammar is often quite easy, but one also has to prove that no string can be derived that is not in the language. For Type-1, this requires some slightly sophisticated arguments that the example on the CSL page more or less provides, but really not that rigorously (but that's not my problem because someone else did that page :).

I think a lot of textbooks prove this by invoking the theorem that monotonic grammars (length of LHS not longer than length of RHS) are equivalent to CSL (with a bit of fiddling to deal with the empty string epsilon. Those grammars are fairly obvious so are almost as easy to prove correct as the Type-3 and Type-2 grammars.

Type-0 is hopeless. The example given (Turing machines that halt) is more or less the classic, but a grammar for that has to essentially be the equivalent of a universal Turing machine description. That is not something to put on a summary page like the Chomsky hierarchy page.

Let me look for references for the examples. When I tried to find a proof last night for Type-1, most things that came up were the monotonic grammars proofs, which had productions such as CB -> BC that are not allowed in CSL but are allowed in monotonic. Ksbooth (talk) 06:06, 21 January 2024 (UTC)[reply]

From my limited observations, the sourcing requirement usually plays a more important role in controversial topics (e.g. politics and biographies). A lot of correct but unsourced content gets kept in CS because informed editors know they're right and don't challenge them. Still, unsourced content is hard to verify and, as you said, could contain imprecisions that are known only to people who specialize in that subfield. Having a published source to back things up is reassuring.

Unfortunately, I'm not too familiar with formal languages and it's also not my main area of Wikipedia edits, but it's really nice to see you improving these articles. Maybe I will also jump on this article again someday when I have the time. PetraMagna (talk) 04:53, 22 January 2024 (UTC)[reply]

There are now examples for Type-3, Type-2, and Type-1. The Type-1 is the same example given on the context-sensitive grammar page, to which there is a reference. That sort of punts the problem, but there is more or less a proof (or at least proof sketch) on the latter describing how the grammar works. Ksbooth (talk) 05:15, 22 January 2024 (UTC)[reply]