3 ms·

You can't always give me a larger HTML document - eventually you will run out of usable universe. Yes, I should have said 'bounded by some finite maximum size'

by nmadden 11y ago

You can't always give me a larger HTML document - eventually you will run out of usable universe. Yes, I should have said 'bounded by some finite maximum size' rather than just finite, but it's not a great leap to see that in reality all documents will be bounded by such a maximum. Finite state automata do indeed need an exponentially larger number of states compared to a pushdown automata, I made no claim as to efficiency. The point remains - for all practical purposes, you can consider all languages to be regular and using a stack is merely an optimisation.

colanderman 11y ago
For practical purposes, expressing your language using an exponentially large number of states is, for the very reasons you state, untenable.
- nmadden 11y ago
  Sure, but that doesn't change the fact that you cannot implement anything at all that accepts more than a regular language. In practice, however you implement it, you will have only implemented something equivalent to some finite state machine (due to the finite memory available to you).
minitech 11y ago
> The point remains - for all practical purposes, you can consider all languages to be regular and using a stack is merely an optimisation. This is thoroughly wrong. For “all practical purposes”, you won’t expand a non-regular language into a giant regular one with an emulated state.
- nmadden 11y ago
  You are confusing regular language with finite state machine. I don't know why there is so much resistance to this. All real machines have bounded memory available to them, thus they can only accept regular languages. Therefore, regular expressions are as powerful as any machine in existence.
  - nmadden 11y ago
    Thinking about this some more, there is no reason that a large number of states has to have a proportional amount of memory. If the states are represented in binary notation (thus needing logarithmic number of bits) and the state transition function is represented as a binary decision diagram then this could be quite compressed indeed.
    - minitech 11y ago
      Interesting idea! Wait, here’s another: maybe you could take your regular grammar that accepts some large number of things that a context-free grammar it’s emulating would accept, and implement it using a stack or something. That would save space and remove the arbitrary restriction.
      - nmadden 11y ago
        Well you can keep picking nits about implementation choices, but unless your stack can grow unbounded (because you have unlimited resources) then you haven't implemented a PDA and haven't removed any restriction at all. You've just optimised space usage. If you really believe that regular expressions cannot parse any HTML document in reality (eg given that all web browsers in practice limit the nesting depth of HTML) then please present some evidence.
        minitech 11y ago
        > If you really believe that regular expressions cannot parse any HTML document in reality (eg given that all web browsers in practice limit the nesting depth of HTML) then please present some evidence. You can build a regular expression to match any HTML document to any fixed depth. Set that to whatever you think “all web browsers” limit HTML nesting to “in practice” – citation very much needed, I don’t believe they do – and voilà! You have produced something absolutely useless and probably several million characters long. I don’t know what you’re arguing. I don’t think you know what you’re arguing either. It’s pointless to continue talking.

by nmadden 11y ago

colanderman 11y ago

For practical purposes, expressing your language using an exponentially large number of states is, for the very reasons you state, untenable.

nmadden 11y ago
Sure, but that doesn't change the fact that you cannot implement anything at all that accepts more than a regular language. In practice, however you implement it, you will have only implemented something equivalent to some finite state machine (due to the finite memory available to you).

minitech 11y ago

> The point remains - for all practical purposes, you can consider all languages to be regular and using a stack is merely an optimisation. This is thoroughly wrong. For “all practical purposes”, you won’t expand a non-regular language into a giant regular one with an emulated state.

nmadden 11y ago
You are confusing regular language with finite state machine. I don't know why there is so much resistance to this. All real machines have bounded memory available to them, thus they can only accept regular languages. Therefore, regular expressions are as powerful as any machine in existence.
- nmadden 11y ago
  Thinking about this some more, there is no reason that a large number of states has to have a proportional amount of memory. If the states are represented in binary notation (thus needing logarithmic number of bits) and the state transition function is represented as a binary decision diagram then this could be quite compressed indeed.
  - minitech 11y ago
    Interesting idea! Wait, here’s another: maybe you could take your regular grammar that accepts some large number of things that a context-free grammar it’s emulating would accept, and implement it using a stack or something. That would save space and remove the arbitrary restriction.
    - nmadden 11y ago
      Well you can keep picking nits about implementation choices, but unless your stack can grow unbounded (because you have unlimited resources) then you haven't implemented a PDA and haven't removed any restriction at all. You've just optimised space usage. If you really believe that regular expressions cannot parse any HTML document in reality (eg given that all web browsers in practice limit the nesting depth of HTML) then please present some evidence.
      - minitech 11y ago
        > If you really believe that regular expressions cannot parse any HTML document in reality (eg given that all web browsers in practice limit the nesting depth of HTML) then please present some evidence. You can build a regular expression to match any HTML document to any fixed depth. Set that to whatever you think “all web browsers” limit HTML nesting to “in practice” – citation very much needed, I don’t believe they do – and voilà! You have produced something absolutely useless and probably several million characters long. I don’t know what you’re arguing. I don’t think you know what you’re arguing either. It’s pointless to continue talking.