Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [fl.formal-languages]

formal languages, grammars, automata theory

Filter by
Sorted by
Tagged with
0 votes
0 answers
14 views

Formalities on loop invariant - algorithms

When proving an algorithm using a loop invariant, we need to check these three things. The loop invariant holds before the loop is entered (initialization) If the loop invariant holds before the loop ...
Agustin G.'s user avatar
2 votes
1 answer
78 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 ...
Navvye's user avatar
  • 21
4 votes
0 answers
134 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)\...
LegionMammal978's user avatar
1 vote
0 answers
59 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 ...
Jerry Ding's user avatar
5 votes
2 answers
147 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 ...
Jerry Ding's user avatar
13 votes
4 answers
977 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 ...
NerdOnTour's user avatar
10 votes
5 answers
297 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#...
TomKern's user avatar
  • 489
11 votes
2 answers
292 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 ...
a3nm's user avatar
  • 9,449
3 votes
1 answer
173 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 ...
TomKern's user avatar
  • 489
8 votes
3 answers
329 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 ...
Satwik's user avatar
  • 181
6 votes
0 answers
75 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, ...
gsv's user avatar
  • 421
2 votes
1 answer
296 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 ...
user avatar
0 votes
0 answers
47 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 ...
J.Doe's user avatar
  • 1
-1 votes
1 answer
82 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 ...
Vetrivel's user avatar
1 vote
1 answer
215 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, ...
Abced Decba's user avatar
7 votes
1 answer
160 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 ...
Rémi's user avatar
  • 262
2 votes
0 answers
182 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]". ...
Martin Dvorak's user avatar
4 votes
3 answers
150 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 ...
uhbif19's user avatar
  • 315
3 votes
1 answer
144 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. ...
Pietro Braione's user avatar
7 votes
1 answer
240 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)$. ...
Janmar's user avatar
  • 135
0 votes
0 answers
73 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 ...
bcarlborg's user avatar
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, ...
voltas1231's user avatar
5 votes
0 answers
80 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 ...
TomKern's user avatar
  • 489
0 votes
1 answer
70 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 ...
Serge's user avatar
  • 111
1 vote
1 answer
225 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 ...
throwaway-grammars's user avatar
3 votes
1 answer
227 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 ...
Janmar's user avatar
  • 135
4 votes
1 answer
179 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 ...
sligocki's user avatar
  • 302
4 votes
0 answers
135 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 ...
Adalynn's user avatar
  • 141
4 votes
1 answer
102 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 ...
WangAtChicago's user avatar
5 votes
1 answer
108 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 ...
WangAtChicago's user avatar
6 votes
0 answers
258 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 ...
Henning's user avatar
  • 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 ...
Ondřej Guth's user avatar
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 ...
Alberto's user avatar
  • 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 $\...
user326210's user avatar
0 votes
1 answer
225 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....
Anonymous's user avatar
9 votes
1 answer
279 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)$...
Ilkka Törmä's user avatar
5 votes
2 answers
229 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 ...
jrwdupl-youtubeyahoocouk's user avatar
1 vote
1 answer
141 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 ...
RockyBilboa's user avatar
8 votes
1 answer
185 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 ...
Denis's user avatar
  • 8,893
6 votes
0 answers
235 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: \{...
Steven Schaefer's user avatar
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} \...
Johan's user avatar
  • 161
6 votes
1 answer
212 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}= \...
thibo's user avatar
  • 193
7 votes
2 answers
157 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 ...
Nicola Gigante's user avatar
3 votes
1 answer
609 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.
Arka's user avatar
  • 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 ...
deryll's user avatar
  • 11
6 votes
1 answer
229 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 ...
Henning's user avatar
  • 59
7 votes
1 answer
173 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 ...
Ignirion's user avatar
5 votes
2 answers
223 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 ...
Bartosz Bednarczyk's user avatar
1 vote
0 answers
86 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 $\...
naloa's user avatar
  • 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 ...
naloa's user avatar
  • 61

1
2 3 4 5
10