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 924
formal languages, grammars, automata theory
3
votes
What can I say about the Parikh map of a CSL?
Regarding the second part of your question: If you choose your CFL $L$ to be the set of all invalid computations of a Turing machine $M$ (see, e.g., Chapter 8.6 in the first edition of "Introduction t …
7
votes
Regular expressions without union but with backreferences
If you are allowed to use complementation to express $\Sigma^*$ as $\emptyset^{C}$, the resulting language class includes the pattern languages (see, e.g., this survey by Kai Salomaa).
As shown by An …
24
votes
A "simple" language outside $CFL \cup coCFL$?
How about $L:=\{a^{n^2}\mid n\in\mathbb{N}\}$? It is easy to see that $L$ and its complement are not regular, and hence (as we are dealing with a unary alphabet) not context-free.
7
votes
Is it possible to represent a regular expression with bounded captures using a DFA and O(1) ...
I have no direct answer, but some additional remarks regarding on the topicality of my paper from this year's STACS which Raphael mentioned in his answer. (Due to space reasons, I opted for a new ans …
12
votes
Accepted
The class CFL\cap co-CFL
For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.
4
votes
Accepted
Equivalence problem for one-counter automata
I have no time to check the references in detail, but Ibarra states in http://dx.doi.org/10.1007/BF01744294 that, according to
Greibachand Baker and Book, the universe problem (is the language $\Sigm …
19
votes
Regular expressions aren't
These expressions have been examined by Aho (Handbook of Theoretical Computer Science, Vol. A, Chp. 5) and Campeanu, Salomaa, Yu ("A formal study of practical regular expressions", International Journ …