Questions tagged [fl.formal-languages]
formal languages, grammars, automata theory
441
questions
6
votes
0
answers
64
views
Updating (minimal) DFA incrementally
Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
- 421
2
votes
1
answer
277
views
Deciding finiteness of regular language is NL-complete?
I've been reading the following Habilitation thesis where the author claims (pg. 29):
... First, deciding whether the language of an NFA is finite is in NL ...
I'm having trouble seeing why this ...
user70406
0
votes
0
answers
46
views
Proving the Equivalence of REGEX r^n and r^{..n} when r Is Nullable
Im seeking clarification and a rigorous proof regarding the equivalence of r^n and r^{..n} in the context of formal languages, particularly when r is nullable.
To clarify the terminology:
r denotes ...
- 1
-1
votes
1
answer
71
views
Generating grammar from a string
Given a string generated with a valid grammar, how can I find list of all the valid grammar for that particular string?
Problem statement - I'm trying to build a code base scanner, and I'd like to ...
- 99
1
vote
0
answers
91
views
Equivalence between GNFA and NFA/DFA
In Section 1.3 of the 3rd edition of Michael Sipser’s Introduction to the Theory of Computation, it is proven that regular expressions are equivalent to deterministic finite automatas (DFAs). That is, ...
- 111
7
votes
1
answer
151
views
Complexity of the inevitability problem over monoids
I am interested in the complexity of following problem:
Inevitability problem in monoids
Input: two regular languages $K$, $L$ specified by finite monoids $M_K$ and $M_L$ (+ morphisms and accepting ...
- 143
2
votes
0
answers
154
views
Semi-Thue systems and deterministic computation
I would like to use semi-Thue systems (a.k.a. string rewriting systems) to study complexity theory formally. Note that "semi-" in the name means "unidirectional [Thue system]".
...
3
votes
3
answers
110
views
Formalization of matching logic (logic behind K Framework)
Is there any mechanization for matching logic (any flavor)?
I only find study about K Framework rules to Deducti translation, but this is both not covering to matching logic and not internalizing the ...
- 295
3
votes
1
answer
137
views
What is the solution of this equation on regular languages?
I need to characterize this language:
$$
L = \{ s \in \Sigma^* \, | \, \{s\} \cdot A_1 \subseteq B_1 \land \ldots \land \{s\} \cdot A_n \subseteq B_n \}
$$
where $A_i, B_i$ are all regular languages. ...
- 133
7
votes
1
answer
227
views
Is DFA language inclusion decidable in quasi-linear time? [duplicate]
Given two DFAs $A_1$ and $A_2$, we want to decide whether $\mathcal{L}(A_1) \subseteq \mathcal{L}(A_2)$. Of course, one can compute whether $\mathcal{L}(A_1) \cap \mathcal{L}(A_2) = \mathcal{L}(A_1)$. ...
- 135
0
votes
0
answers
62
views
Are there data structures that cannot be serialized / deserialized using a context free grammar?
I understand that deserializing data from a string or binary stream into a data structure is effectively the same parsing. When you deserialize the input string, you use a grammar to create a parse ...
11
votes
12
answers
5k
views
Theoretical Computer Science vs other Sciences?
So I‘m in my fifth semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, ...
- 127
4
votes
0
answers
71
views
Equivalent Characterizations of Semilinear Sets
Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations.
I am already familiar with a few well known ones:
Sets ...
- 279
0
votes
1
answer
68
views
Proper terminology for input, parameter or variable fixing. Refinement? Projection? Fixation? Partial valuation?
I contemplate writing a paper on automating fixing some inputs/parameters to specific values in a kind of workflow/pipeline definition language/system and looking for best terminology.
English is not ...
- 111
1
vote
1
answer
145
views
Can an unrestricted grammar have a rule with only terminals on the left-hand side?
In the definition of unrestricted (type 0) grammars we only really have the rule that the lhs cannot be the empty string.
Then, is it allowed to have a production rule with an lhs consisting only of ...
3
votes
1
answer
195
views
Algorithms for equivalence of 2 way finite automata (2DFA)
I'm interested in the computational complexity of deciding equivalence of 2DFAs.
It is known that converting 2DFA to DFA can incur a blow up in states. However I'm not sure whether this automatically ...
- 135
3
votes
1
answer
165
views
Subset of regular languages
I have a system that is deciding a subset of regular languages and am curious if anyone has seen this type before and if it has a name I could use to research more.
Specifically consider the ...
- 292
4
votes
0
answers
126
views
Languages recognized Counter DFA
I just randomly started fooling around with formal languages, grammars, and machines, and I have an extension to DFAs that I do not know what the class of languages it can recognize is.
I'll give a ...
- 141
4
votes
1
answer
96
views
Is there any context-free language that is inherently ambiguous as an indexed language
Indexed languages are defined as being produced by indexed grammar.
Is there any context-free language that is inherently ambiguous as an indexed language? That is, is there a context-free language ...
- 101
5
votes
1
answer
106
views
Is there any inherently ambiguous indexed language?
Indexed languages are defined as being produced by an indexed grammar.
My question is: Is there an indexed language such that there is no indexed grammar that can produce every word of the language in ...
- 101
6
votes
0
answers
252
views
Context Free Grammar For Complement Of { wwwww | ... } With Minimal Locality?
Definitions
Let $G$ be a context free grammar over an alphabet $\Sigma$ with non-terminals $V$.
Define the locality $l(G)$ as the length of the longest word in $(V \cup \Sigma)^*$ that has a ...
- 59
1
vote
0
answers
159
views
Can we describe any context-sensitive language by a grammar without left recursion?
The main question: is it possible to avoid left recursion in a context-sensitive grammar (see example below), i.e., if for any context-sensitive language $L$, there exists some context-sensitive ...
- 11
2
votes
0
answers
79
views
Nondeterministic polynomial time languages with linearly bounded certificates
Define the class $X$ of languages by the condition that a language $L$ over alphabet $\Sigma$ is in $X$ iff there are a constant $c > 0$ and a polynomial-time checking relation $R$ such that for ...
- 191
5
votes
1
answer
168
views
Establishing competing memory limits for pushdown automata
Let $L$ be the language of all even-length strings whose first half is a palindrome.
Let $L$ be the language of all even length strings whose first half is imbalanced—with an unequal number of $\...
- 151
0
votes
1
answer
178
views
Where to read about PSO (partial store order) memory model
I have been reading about TSO (total store order) memory models for concurrent programs, but I can not find resources for PSO (partial store order) memory models. Can someone please point to resources....
9
votes
1
answer
260
views
Words of the form $(a^n b)^n$ in a context-free language
Question
For a language $L \subset \{a,b\}^*$, denote $N(L) = \{ n \geq 0 \mid (a^n b)^n \in L \}$.
If $L$ is context-free, is $N(L)$ necessarily semilinear, meaning that $n \in N(L) \iff n+p \in N(L)$...
- 661
5
votes
2
answers
221
views
Are trace monoids always syntactic monoids?
There's an assertion on Wikipedia that a trace monoid is a syntactic monoid because $x w y \equiv x v y$ implies that $w \equiv v$. I don't see how that follows as a consequence, and I can't find any ...
1
vote
1
answer
136
views
Bounded non-emptiness intersection of deterministic context-free grammars
Let A and B be two determinstic context-free grammar, and let N be an integer: What's the complexity of deciding if the intersection of the languages accepted by A and B over all strings of length ...
- 11
8
votes
1
answer
177
views
Word equations with integer parameters
This is mainly a reference request.
Let us define a parameterized expression on a finite alphabet $\Sigma$ as follows:
$$e,e':= w\mid w^i \mid e\cdot e'$$
Where $w\in\Sigma^+$ is a word, and $i$ is an ...
- 8,598
6
votes
0
answers
229
views
Satisfiability and a Galois Theory Analog
Let $v(a, b)$ be a binary predicate, and define $\phi$ as follows:
$$\phi: v(a_1, b_1) \land v(a_1, b_2) \land (a_1, b_3)$$
where our universe consists of two sorts $A: \{a_1, a_2, a_3\}$ and $B: \{...
5
votes
1
answer
213
views
Name for words without squared symbols
Is there a common name in combinatorics for words that do not have square of size 1 ? That is words such that no symbols appears twice in a row or, more formally, words not in $\bigcup_{s\in\Sigma} \...
- 161
6
votes
1
answer
203
views
star height of star-free languages
I'm interested in the (restricted) star-height of star free-languages.
Recalling the definitions:
the star height $h(\mathtt{e})$ of a regular expression $\mathtt{e}$ is
$0$ if $\mathtt{e}= \...
- 193
7
votes
2
answers
156
views
Algebraic characterisation of star-free safety languages
It is known that star-free languages are definable by aperiodic syntactic monoids.
But is there any algebraic characterisation of star-free safety $\omega$-languages?
Edit: A language $L$ is safety if ...
- 1,588
3
votes
1
answer
598
views
Determinising unambiguous automata without exponential blowup
Is it possible to determinise unambiguous finite automata without exponential blowup in the number of states? I think it should not be possible but I am unable to come up with counterexamples.
- 131
1
vote
0
answers
79
views
Parametrization of context-sensitive language in polynomial time
Let $\Sigma$ be a finite alphabet. Let $L\subset \Sigma^*$ be a context-sensitive language containing a word of every length.
Can we always find $f:\Sigma^*\to L$ computable in polynomial time in ...
- 11
6
votes
1
answer
215
views
Context Free Grammar For Complement Of { www | ... } with minimal pumping length?
Let $L := \{ w^3 | w \in \{0,1\}\}^C$ be the complement of the language of words that are not the 3rd power of a word over $\Sigma = \{0,1\}$.
Let's define the largest minimal pumping length of a ...
- 59
7
votes
1
answer
170
views
Example of an context-sensitive language with a specific number of words of length $n$
Let $s_L(n)$ denote the number of words of length $n$ in $L$.
For context-free languages it is known that $s_L(n)$ is either polynomial or exponential.
For context-sensitive languages this is probably ...
- 73
5
votes
2
answers
216
views
Reference request: An algebraic characterisation of LTL[XF]-definable word languages
I'm looking for a reference to the fact that LTL[XF]-definable languages (LTL where only the (strict) finally/future modality is allowed) correspond to the variety $\mathbf{R}$ (see: 1).
A similar ...
- 1,320
1
vote
0
answers
84
views
Take a natural quotient of context-free grammars
Fix a finite alphabet.
Let $\mathrm{CFG}$ be the set of context-free grammars on this alphabet, $\mathrm{CFL}$ the set of context-free languages, $\mathrm{UG}$ the set of unrestricted grammars and $\...
- 61
5
votes
0
answers
98
views
Useful notion of ambiguous growing context-sensitive language
As far as I understand there is no useful notion of ambiguous context-sensitive language.
For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
- 61
0
votes
1
answer
136
views
Reference for context-free grammar for Martin-Löf type theory
Are the terms and the types of Martin-Löf type theory described by context-free grammars? Have such grammars been written down somewhere?
- 11
10
votes
1
answer
821
views
Ambiguity of regular expressions
Some regular expressions are ambiguous. Some are not. a*b* is unambiguous for example. Expression a*a* is ambiguous but it can ...
- 481
3
votes
1
answer
103
views
Conditioning Probability on a Language With Measure 0
Let $\Sigma = \{ 1, 2, \ldots, n\}$ be some alphabet. Assume that you have a coin with n-sides (each side corresponds to a letter in $\Sigma$), and we get each letter with equal probability. Now you ...
- 257
4
votes
0
answers
77
views
Terminology for languages of pairs of words
I want to consider $L \subset A^* \times B^*$ as a "language". Is there standard terminology for this?
I wrote "double language" first (but that doesn't sound right to me), then &...
- 521
2
votes
0
answers
100
views
Necessary and sufficient condition for an infinite tree to be context-free
A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...
- 193
4
votes
1
answer
706
views
Can we efficiently convert from NFA to smallest equivalent DFA?
Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.
...
- 5,127
1
vote
1
answer
91
views
Definition of Rabin acceptance condition for omega automatons [closed]
I've been trying hard to understand something. According to wikipedia and this paper, the definition of the Rabin acceptance condition involves a set of pairs of states. I've been told that the left ...
- 111
0
votes
1
answer
58
views
Reduction of a language to a shorter equivalent [closed]
I'm new to Theoretical Computer Science, and my textbook says that it is easy to verify that the following language
\begin{array}{l}
L_{1}=A^{*} \cdot\{b\}-\left(A^{*} \cdot(A-\{a\}) \cdot A^{*} \cdot\...
- 119
5
votes
1
answer
145
views
Different definitions of grammar complexity
It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
- 411
5
votes
1
answer
102
views
Nonterminal descriptional complexity of regular languages
Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below.
I am aware of an ...
- 411