5 ms·

Not sure about regex. Its syntax is, by definition, regular. (Okay, most regex engines people use aren’t technically fully regular languages anymore, but that j

by anyfoo 1y ago

Not sure about regex. Its syntax is, by definition, regular. (Okay, most regex engines people use aren’t technically fully regular languages anymore, but that just makes things more convenient.)

eru 1y ago
> Its syntax is, by definition, regular. No, not at all. Regexes describe regular languages, but that doesn't mean that their own syntax needs to be a regular language. Eg many regexes allow parens, so you can have both 'ab|c' and 'a(b|c)'. But if you require your parens to be balanced, that's no longer a regular language.
- skissane 1y ago
  > But if you require your parens to be balanced, that's no longer a regular language From a certain pedantic perspective, it still is a regular language, since there is a finite (implementation dependent) upper bound on nesting depth, and balanced parens with a finite upper bound of nesting is regular. OTOH, one can appeal to the linguistic distinction between competence and performance, and say that regexes are irregular in pure competence, even though all (practically usable) languages turn out to be regular once we constrain them by performance as well.
  - eru 1y ago
    > From a certain pedantic perspective, it still is a regular language, since there is a finite (implementation dependent) upper bound on nesting depth, and balanced parens with a finite upper bound of nesting is regular. That's a silly point, because it makes all languages trivially finite, even monsters like C++. (Finity is even more of a restriction than being regular.)
    - skissane 1y ago
      Is it silly? Well, if a person feels drawn to an ultrafinist philosophy of mathematics, they may feel it is important to emphasise the inherent finitude of all creations of inherently finite human minds, formalisms such as programming languages included.
      - eru 1y ago
        Oh, finitism is perfectly fine by me. I have a lot of sympathy for it! What is silly is not finitism (or ultrafinitism), but trying to apply concepts like 'regular language' or 'context free language' without modification in such a setting. I suspect you should be able to suitably alter most of these concepts to make sense in the strictly finite setting. But they are going to become a lot more complicated. For a similar flavour, you can also check out the differences and similarities between differential equations and difference equations.
        skissane 1y ago
        Right, but the “finite setting” is the real world. Yes, if we talk about C++ as a mathematical abstraction, maybe a C++ program containing a googolplex tokens could be in a theoretical sense syntactically and semantically valid. But such a program can’t exist in the real world Let’s say a compiler has a (very plausible) implementation restriction that the source code of a program can be no longer than 2^32 bytes. Then, even if the abstract grammar is (e.g.) an unbounded context-free language, the actually accepted language has a finite upper bound on length-and it is well-known that applying a length constraint turns a context-free language into a regular language. This doesn’t require us to “to suitably alter most of these concepts to make sense in the strictly finite setting”, because formal language theory in an infinite setting permits constraining languages to be finite, and we have a very good understanding of what that the results of that are - this doesn’t require any new or different math, just applying the same math. Now, it is true that, we will say that certain algorithms only work for regular languages, not context-free - but once we impose a finite bound on length, those algorithms do actually work in principle. In practice, of course, they are likely impractically slow - but the formalism we are talking about (the Chomsky hierarchy) is based on computability (can it answer the question in a finite but unbounded amount of time), not asymptotic computational complexity (nor real-world performance, which isn’t the same thing, as e.g. galactic algorithms demonstrate)
        eru 1y ago
        And those formalisms all become silly. Computability also becomes trivial, if you only have a finite amount of memory: either your program halts after a finite amount of time, or it enters a loop after at most 2^(number of bits in your memory) steps.
- anyfoo 1y ago
  You're right!
- eterm 1y ago
  > if you require your parens to be balanced, that's no longer a regular language. TIL: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang... As someone who has only recently learned the formal definition of regular language ( Thanks to https://www.youtube.com/watch?v=9syvZr-9xwk https://www.youtube.com/watch?v=9syvZr-9xwk as mentioned on this board recently ), I'm interested in the formal proof for this? It feels intuitively true, but I haven't finished the course yet and therefore haven't come across it and can't yet reason well about it. Is the problem then in trying to "encode" whether brackets are balanced, that we would need infinite "levels" of how many more brackets we've opened rather than closed, (i.e a stack) and that violates the finite nature of finite automota? So I've googled it now, and I've found the result is due to the "Pumping lemma": https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...
  - gbacon 1y ago
    Pulling on the thread of your intuition about needing infinite levels, a regular language is one that can be recognized by a finite automaton, so requiring infinite memory or arbitrarily high counting suggests that the language is not regular. It’s not perfect; we prove it as below. Assume for purpose of contraction that our language L of balanced parentheses is regular. Then L has pumping length p ≥ 1 such that every w ∈ L where |w| ≥ p can be decomposed w = xyz where |y| ≥ 1 and |xy| ≤ p. It is called the pumping lemma because we can “pump” the non-empty substring y either up or down, i.e., xy⁰z = xz and xyⁿz are also all in L. In formal languages, exponentiation notates character or string repetition. We don’t know p and may not cherry pick it. Pretend you are playing a game against an adversary who gets to select arbitrary p ≥ 1, and then you use that p to choose w ∈ L to spoil the regular language party. With the language of balanced parentheses, no matter what p the adversary selects, you can force the leading xy prefix to contain all left-parentheses by choosing w = (ᵖ)ᵖ. The substring y cannot be empty, so pumping down gives xy⁰z = (ᵖ⁻ᵏ)ᵖ belongs to L, a contradiction. One of my favorite test questions for automata theory classes is to have ChatGPT attempt a proof that a language is not regular and then have students correct the proof. You linked to a lecture by Michael Sipser, and the undergraduate version of the course I teach uses his excellent textbook. https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X https://www.amazon.com/Introduction-Theory-Computation-Micha... His lecture on the pumping lemma for regular languages is https://youtu.be/KAySmSEGc9U?t=1807 https://youtu.be/KAySmSEGc9U?t=1807

by anyfoo 1y ago

Not sure about regex. Its syntax is, by definition, regular. (Okay, most regex engines people use aren’t technically fully regular languages anymore, but that just makes things more convenient.)

eru 1y ago

> Its syntax is, by definition, regular. No, not at all. Regexes describe regular languages, but that doesn't mean that their own syntax needs to be a regular language. Eg many regexes allow parens, so you can have both 'ab|c' and 'a(b|c)'. But if you require your parens to be balanced, that's no longer a regular language.

skissane 1y ago
> But if you require your parens to be balanced, that's no longer a regular language From a certain pedantic perspective, it still is a regular language, since there is a finite (implementation dependent) upper bound on nesting depth, and balanced parens with a finite upper bound of nesting is regular. OTOH, one can appeal to the linguistic distinction between competence and performance, and say that regexes are irregular in pure competence, even though all (practically usable) languages turn out to be regular once we constrain them by performance as well.
- eru 1y ago
  > From a certain pedantic perspective, it still is a regular language, since there is a finite (implementation dependent) upper bound on nesting depth, and balanced parens with a finite upper bound of nesting is regular. That's a silly point, because it makes all languages trivially finite, even monsters like C++. (Finity is even more of a restriction than being regular.)
  - skissane 1y ago
    Is it silly? Well, if a person feels drawn to an ultrafinist philosophy of mathematics, they may feel it is important to emphasise the inherent finitude of all creations of inherently finite human minds, formalisms such as programming languages included.
    - eru 1y ago
      Oh, finitism is perfectly fine by me. I have a lot of sympathy for it! What is silly is not finitism (or ultrafinitism), but trying to apply concepts like 'regular language' or 'context free language' without modification in such a setting. I suspect you should be able to suitably alter most of these concepts to make sense in the strictly finite setting. But they are going to become a lot more complicated. For a similar flavour, you can also check out the differences and similarities between differential equations and difference equations.
      - skissane 1y ago
        Right, but the “finite setting” is the real world. Yes, if we talk about C++ as a mathematical abstraction, maybe a C++ program containing a googolplex tokens could be in a theoretical sense syntactically and semantically valid. But such a program can’t exist in the real world Let’s say a compiler has a (very plausible) implementation restriction that the source code of a program can be no longer than 2^32 bytes. Then, even if the abstract grammar is (e.g.) an unbounded context-free language, the actually accepted language has a finite upper bound on length-and it is well-known that applying a length constraint turns a context-free language into a regular language. This doesn’t require us to “to suitably alter most of these concepts to make sense in the strictly finite setting”, because formal language theory in an infinite setting permits constraining languages to be finite, and we have a very good understanding of what that the results of that are - this doesn’t require any new or different math, just applying the same math. Now, it is true that, we will say that certain algorithms only work for regular languages, not context-free - but once we impose a finite bound on length, those algorithms do actually work in principle. In practice, of course, they are likely impractically slow - but the formalism we are talking about (the Chomsky hierarchy) is based on computability (can it answer the question in a finite but unbounded amount of time), not asymptotic computational complexity (nor real-world performance, which isn’t the same thing, as e.g. galactic algorithms demonstrate)
        eru 1y ago
        And those formalisms all become silly. Computability also becomes trivial, if you only have a finite amount of memory: either your program halts after a finite amount of time, or it enters a loop after at most 2^(number of bits in your memory) steps.
anyfoo 1y ago
You're right!
eterm 1y ago
> if you require your parens to be balanced, that's no longer a regular language. TIL: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang... As someone who has only recently learned the formal definition of regular language ( Thanks to https://www.youtube.com/watch?v=9syvZr-9xwk https://www.youtube.com/watch?v=9syvZr-9xwk as mentioned on this board recently ), I'm interested in the formal proof for this? It feels intuitively true, but I haven't finished the course yet and therefore haven't come across it and can't yet reason well about it. Is the problem then in trying to "encode" whether brackets are balanced, that we would need infinite "levels" of how many more brackets we've opened rather than closed, (i.e a stack) and that violates the finite nature of finite automota? So I've googled it now, and I've found the result is due to the "Pumping lemma": https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...
- gbacon 1y ago
  Pulling on the thread of your intuition about needing infinite levels, a regular language is one that can be recognized by a finite automaton, so requiring infinite memory or arbitrarily high counting suggests that the language is not regular. It’s not perfect; we prove it as below. Assume for purpose of contraction that our language L of balanced parentheses is regular. Then L has pumping length p ≥ 1 such that every w ∈ L where |w| ≥ p can be decomposed w = xyz where |y| ≥ 1 and |xy| ≤ p. It is called the pumping lemma because we can “pump” the non-empty substring y either up or down, i.e., xy⁰z = xz and xyⁿz are also all in L. In formal languages, exponentiation notates character or string repetition. We don’t know p and may not cherry pick it. Pretend you are playing a game against an adversary who gets to select arbitrary p ≥ 1, and then you use that p to choose w ∈ L to spoil the regular language party. With the language of balanced parentheses, no matter what p the adversary selects, you can force the leading xy prefix to contain all left-parentheses by choosing w = (ᵖ)ᵖ. The substring y cannot be empty, so pumping down gives xy⁰z = (ᵖ⁻ᵏ)ᵖ belongs to L, a contradiction. One of my favorite test questions for automata theory classes is to have ChatGPT attempt a proof that a language is not regular and then have students correct the proof. You linked to a lecture by Michael Sipser, and the undergraduate version of the course I teach uses his excellent textbook. https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X https://www.amazon.com/Introduction-Theory-Computation-Micha... His lecture on the pumping lemma for regular languages is https://youtu.be/KAySmSEGc9U?t=1807 https://youtu.be/KAySmSEGc9U?t=1807