Questions tagged [fl.formal-languages]
formal languages, grammars, automata theory
454
questions
0
votes
0
answers
31
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
206
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
86
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
136
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
68
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
152
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
13
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 ...
- 233
10
votes
5
answers
315
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#...
- 489
11
votes
2
answers
301
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,677
3
votes
1
answer
177
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 ...
- 489
8
votes
3
answers
342
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
314
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