Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with fl.formal-languages
Search options answers only
not deleted
user 657
formal languages, grammars, automata theory
8
votes
Algebraic data type - rewrite system
The answer to your question is yes. Unification modulo an ACU (associative, commutative, unital) operator is decidable. See Baader and Snyder's chapter "Unification Theory" in the Handbook of Automate …
- 32.9k
4
votes
Accepted
Regularity of language with finite number of right derivatives
See Janusz Brzozowski's 1964 paper Derivatives of Regular Expressions. This is theorem 5.2 in the paper, and the proof is in Appendix 2.
- 32.9k
19
votes
Accepted
Where do most REGEX implementations fall on the complexity scale?
I don't think that the real problem is the question of what unbounded means; this is no worse than any other situation in parsing.
The trouble lies with characterizing backreferences, which are both …
- 32.9k
2
votes
Looking for menu-driven coding editor based on a programming language state machine
This is a research area that's been investigated quite heavily since the late 1970s. The keyword to Google for is "structure editor", and the great-grandparent of all modern structure editors is the C …
- 32.9k
12
votes
Accepted
Distance between regular languages
As you perhaps already know, a common metric on words is the Cantor metric, which is defined as:
$$
d(l, k) = \left\{ \begin{array}{ll}
0 & \mbox{if } l = k \\
…
- 32.9k
42
votes
Accepted
Does there exist an extension of regular expressions that captures the context free languages?
Yes, there is. Define a context-free expression to be a term generated
by the following grammar:
$$
\begin{array}{lcll}
g & ::= & \epsilon & \mbox{Empty string}\\
& | & c & \mbox{Character …
- 32.9k
4
votes
Brackets expression incremental parsing algorithm
Take a look at Tim Wagner and Susan Graham's 1998 TOPLAS paper, "Efficient and Flexible Incremental Parsing", which extends LR parsing to support incremental update of the document.
- 32.9k
3
votes
Can abstract syntax trees be unparsed in subexponential time?
If the synthesized attributes compute a parse tree, then unparsing can be done in time linear in the size of the parse tree, assuming that string concatenation happens in constant time -- the obvious …
- 32.9k
2
votes
Reference for context-free grammar for Martin-Löf type theory
Generally, there will be one context-free grammar for both types and terms, and judgements will be used to identify those expressions which are types and which expressions are terms of a particular ty …
- 32.9k
21
votes
Accepted
Context Sensitive Grammars and Types
It is not possible for linear bounded automata to check whether C++ programs, and unlikely to be possible for and LBA to check whether SML programs are well-typed. C++ has a Turing-complete type syste …
- 32.9k