101–110 of 224 posts
Earlier quoted context omitted.
Indeed. Type 0 Grammars are the most powerful grammars we have. https://en.wikipedia.org/wiki/Chomsky_hierarchy#Type-0_gramm... In this type of grammar Godel's incompleteness theorem is equivalent to the Halting problem.
And which programming language did you have in mind?
"Type-0 grammars include all formal grammars. They generate exactly all languages that can be recognized by a Turing machine."
Earlier quoted context omitted.
And which programming language did you have in mind?
All of them. "Type-0 grammars include all formal grammars. They generate exactly all languages that can be recognized by a Turing machine."
> Is there a regular expression to detect a valid regular expression? No, there is not. For example, parentheses in a regex must be balanced, and (famously) there is no regex to detect balanced parentheses.
It depends on the representation. If the representation is in the FSA format (state, character, state), it becomes nearly trivial.
Earlier quoted context omitted.
Perhaps the most epic reply I have ever seen on SO.
It’s a famous post on StackOverflow, but I don’t find it particularly helpful.
some people like to act super serious all the time like they're playing a sitcom version of what they think adulthood is in a quest to be the most boring person on earth like if that's the goal of human interaction
Earlier quoted context omitted.
More precisely, it is arbitrarily deep nested clauses that cannot be parsed, on account of true REs not being able to either use recursion or keep count of how deep they are. https://blogs.msdn.microsoft.com/jaredpar/2008/10/15/regular...
Can regex engines actually process arbitrarily deep nestings themselves though? It seems to me it would start getting computationally expensive very quickly to search for those kinds of regexes, so is 'arbitrarily deep' a practical concern for todays hardware?
One such engine is rust's https://github.com/rust-lang/regex
Earlier quoted context omitted.
A parser. Specifically, an XHTML parser.
How do you think an XHTML parser is written? In particular, how does an XHTML parser identify tokens like start and end tags?
[1] https://en.m.wikipedia.org/wiki/Pushdown_automaton
[2] https://en.m.wikipedia.org/wiki/Linear_bounded_automaton
More specifically, a stack lets you keep track of nesting. See an opening tag, push something onto a stack. See a closing tag, pop the stack. If the stack is empty at the end, the tags match.
Parsing XHTML in real life is of course much more complicated than this, but this is the basic idea.
> Is there a regular expression to detect a valid regular expression? No, there is not. For example, parentheses in a regex must be balanced, and (famously) there is no regex to detect balanced parentheses.
It depends on the representation. If the representation is in the FSA format (state, character, state), it becomes nearly trivial.