Questions tagged [fl.formal-languages]
formal languages, grammars, automata theory
456
questions
0
votes
0
answers
34
views
Are there approaches to deriving a Grammar(production rules) from given set of strings?
Apologies for unambiguous question. So far I have a lot of difficulties of discerning on how to design formal production rules for some formal language aside from classic examples such as equal pairs ...
- 9
9
votes
1
answer
261
views
Can we decide the existence of some regular language closed under a Thue system?
Given a regular language $L \subseteq \Sigma^*$ and a finitely presented Thue system $R$ in a finitely extended alphabet $\Sigma' \supseteq \Sigma$, can we decide whether there is a regular language $...
- 91
0
votes
0
answers
37
views
Dependence of lossless compression (e.g. Lempel-Ziv) on string length and alphabet size
Suppose we have a lossless compression algorithm A, which compresses a string of length $n$.The symbols in the string are chosen uniformly at random from an alphabet with cardinality $p$. Different ...
2
votes
0
answers
66
views
Complexity of FirstMatch (Prefix Elimination) Operator for regular expressions
Consider the operator $\texttt{FirstMatch} : 2^{\Sigma^*} \to 2^{\Sigma^*}$ defined as follows:
$$\texttt{FirstMatch}(L) = \left \{ y \mid y \in L, \forall \text{ prefixes } x \text{ of } y, x \not \...
8
votes
1
answer
209
views
A split-consistency property of a formal language
I am looking for occurrences in literature of the following property of a formal language $\mathcal L$ over an alphabet $\Sigma$
For any quadruple of words $a,b,c,d\in\Sigma^*$, if $ac,bc,ad\in\...
- 181
2
votes
1
answer
92
views
Time Complexity of KnuthBendixCompletion Algorithm [closed]
I am currently studying the Knuth-Bendix completion algorithm and trying to understand the factors that contribute to its time complexity. This algorithm is used to transform a set of rewrite rules ...
- 21
4
votes
0
answers
139
views
Learning a regular language with a specified closure property
Consider an alphabet $\Sigma$, and a partial transformation function $f:S\to\Sigma^\ast$ defined on some subset $S\subseteq\Sigma^\ast$. Let $S_f$ denote the set of strings $s\in S$ such that $f^n(s)\...
- 141
1
vote
0
answers
73
views
Not possible to write deterministic CFG for balanced parenthesis?
I know that it's possible to build an LL(1) parser for the Dyck language, i.e. a balanced string of parentheses, so the Dyck language is a deterministic context-free language.
But what's an example of ...
- 163
5
votes
2
answers
155
views
Modify DCFG to enforce length limit
Given a deterministic context-free grammar $G$ that generates the language $L$, is there an efficient algorithm that can be used to construct another DCFG $G_N$ that generates the language $\{ s \in L ...
- 163
15
votes
4
answers
1k
views
List of nice non-context-free languages
I am trying to separate classes of formal languages from each other. One of these classes is the class of context-free languages. To this end, it would be handy to have a list of languages which are ...
- 253
13
votes
5
answers
414
views
Obscure characterizations of the regular languages
I've been collecting equivalent characterizations of the regular languages. Does anyone know of any I haven't yet found?
Wikipedia has a bunch: https://en.wikipedia.org/wiki/Regular_language#...
- 519
12
votes
2
answers
309
views
Is there a simple characterization of regular languages closed under circular shifts?
A language $L$ is closed under circular shifts if, for every word $w = a_1 ... a_n$ and circular shift $w' = a_i ... a_n a_1 ... a_{i-1}$ of $w$, then $w \in L$ iff $w' \in L$. It is equivalent to ...
- 9,697
3
votes
1
answer
180
views
Is it useful to "untangle" an NFA by converting to a regular expression and back
Consider the following recursive algorithm for converting a regular expression into a transition diagram for an NFA with epsilon-edges (freely, optionally traversible edges), one start state and one ...
- 519
8
votes
3
answers
348
views
Relationship between size of Boolean functions and DFAs
Are there any works that study the relationship between Boolean functions and the size of the minimal DFAs required to represent those Boolean functions? Boolean functions refer to the usual ...
- 181
6
votes
0
answers
80
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
316
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
49
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
86
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
1
answer
241
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
163
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 ...
- 262
2
votes
0
answers
210
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]".
...
4
votes
3
answers
166
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 ...
- 315
3
votes
1
answer
147
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
256
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
85
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 ...
13
votes
12
answers
6k
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, ...
- 147
5
votes
0
answers
81
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 ...
- 519
0
votes
1
answer
71
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
250
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
231
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
4
votes
1
answer
190
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 ...
- 302
4
votes
0
answers
142
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
103
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
110
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
260
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
161
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
84
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
173
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
248
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
290
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)$...
- 671
5
votes
2
answers
232
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
146
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
188
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,923
6
votes
0
answers
238
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: \{...
- 101
5
votes
1
answer
214
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
220
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
161
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,704
3
votes
1
answer
615
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
233
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