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 formal-languages
Search options not deleted
user 4600
The study of formal languages (sets of strings or trees over an alphabet), rewriting systems and algorithms, recognition automata/algorithms, and related questions.
6
votes
Accepted
Is this variant of the balanced bracket language context free?
I think it's context-free and generated by roughly speaking the following 7 rules (but see Harry Altman's answer for more precision)
$$S \rightarrow TUT,\quad U\rightarrow [TUT]$$
$$ U\rightarrow e,\q …
- 24.8k
8
votes
Accepted
Is there an unambiguous CFL whose complement is not context-free?
Yes, and the first published example is, in a 4-letter alphabet $\{a,b,c,d\}$, the set of all words $a^pb^qc^rd^s$ such that either
$$
(10p<q<12p\text{ or } 10q<p<12q)\text{ and } (10r<s<12r \text{ or …
- 24.8k
5
votes
Accepted
Every infinite c.e.language is infinite or finite union of regular languages including at le...
A polynomial - time random language will not have any infinite regular subsets, so there's a counter example to the first question.
For a similar counterexample to the second question, we can increa …
- 24.8k
5
votes
Are there any results on well-quasi-ordering of languages?
Does $\stackrel{\mathrm L}{\preceq}$ well-quasi-order the regular languages over $A^*$?
No, let $ L_n $ contain all strings of length $ n $, then the $ L_n $ form an infinite antichain. So $\stac …
- 24.8k
2
votes
Are there any results on well-quasi-ordering of languages?
Does $\stackrel{\mathrm L}{\preceq}$ well-quasi-order the prefix-closed regular languages over $A^*$?
No, let $L_n$ be the set of all prefixes of $0^n10^\infty$. Then the $L_n$ are prefix-closed, …
- 24.8k
3
votes
Accepted
Terminology for set of infinite strings with a certain prefix
Yes, $C(s)$ is an example of a cylinder set.
More specifically, $C(s)$ is called a basic open cylinder (since other cylinder sets are
unions of such sets). See e.g. Andre Nies' monograph Computabili …
- 24.8k