Questions tagged [formal-languages]
The study of formal languages (sets of strings or trees over an alphabet), rewriting systems and algorithms, recognition automata/algorithms, and related questions.
158 questions
2
votes
1
answer
235
views
2
votes
1
answer
133
views
What is the cardinality of the set of Dyck natural numbers of semilength $k$?
In arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I show that there is a 1:1 correspondence between $\mathbb{N} = \{0,1,2,3,4,\ldots\}$ and $\mathcal{D}_{r_{\...
- 129
2
votes
1
answer
1k
views
Proof that the $\omega$-language consisting of all words containing every finite word as a factor is not rational/regular
Let $\eta$ be an $\omega$-word over $X = \{0,1\}$ and let $F_k(\eta)$ denote the factors of $\eta$ of length $k$. Define the following $\omega$-languages
$$
L_k := \{ \xi : F_k(\xi) = X^k \} = \{ \xi ...
- 798
2
votes
1
answer
197
views
Varieties of rational languages and (pseudo-)varieties of finite monoids, question regarding closure property
Let $\mathcal Rat(A)$ denote the class of rational (or regular) languages over the alphabet $A$, a subset $\mathcal V(A) \subseteq \mathcal Rat(A)$ is called a variety of (rational) languages iff
...
- 798
2
votes
1
answer
124
views
Proof of dynamic programming calculation of Levenshtein distance
Let s1 and s2 are 2 arbitrary strings with lengths l1 and ...
- 203
2
votes
1
answer
70
views
For synchronizing eulerian finite state machines every proper subset of states has some larger state set leads to this subset
Suppose we have a deterministic complete finite automaton which is synchronized, meaning we have a reset word, i.e. a word which resets the automaton to a definite state, regardless from which state ...
- 798
2
votes
1
answer
219
views
Alternative notation for Kleene star
I am writing a paper which use two different operations on sets of works $X$, both of which I want to denote by a star, $X^{\ast}$. One of these operations is the Kleene star, and for whatever reason ...
- 21
2
votes
1
answer
143
views
Representability of sets of infinite sequences sharing common prefixes and factors (i.e. infixes)
Here we are concerned with the space $X^{\omega}$ of infinite sequences. Denote by $F_n(\xi)$
the set of factors (consecutive finite subsequences) of length $n$ and consider the set
$$
K_n(\xi) = \xi[...
- 798
2
votes
1
answer
224
views
Parsing of Stochastic Contex-Free Grammars (SCFGs)
I am interested in parsing of general SCFGs.
I am aware of the Earley parser for the general CFGs. The only general algorithm for parsing SCFGs that I am aware of is the Earley-Stolcke parser : http:/...
- 21
2
votes
0
answers
86
views
Rewriting systems for finite groups [closed]
This is a question about rewriting systems & languages for finite groups. I'm sure everything must be in the literature somewhere, but I find it hard to navigate the references I have (for example ...
- 2,287
2
votes
0
answers
64
views
A particular generalization of free partially commutative monoids
A trace monoid, or free partially commutative monoid, is one with the presentation $\langle \Sigma \mid a_1b_1 = b_1a_1, \dots, a_nb_n = b_na_n\rangle$. The theory of trace monoids has been well ...
- 21
2
votes
0
answers
64
views
Polynomial-time algorithm for uniformly sampling the $n$-slice of a context-free language
Let $L\subset \Sigma^*$ be a context-free language. The $n$-slice is the intersection $L\cap \Sigma^n$ for a non-negative integer $n$.
Is there a polynomial-time algorithm for uniformly sampling from ...
- 21
2
votes
0
answers
100
views
Name for the theory of words with equal length, prefix, successors
I've worked with this theory for a while, but I've never been quite sure what to call it:
$$(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$$
Where
$\Sigma^*$ is the set of finite words on finite ...
- 429
2
votes
0
answers
47
views
Relation between indexed languages (OI-macro or context-free tree) and scattered context languages
I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by
scattered context grammars--J Hopcroft).
I think that ...
- 21
2
votes
0
answers
221
views
The Kleene theorem
By the Myhill–Nerode theorem a language $L$ is accepted by a finite automaton iff it consists of classes of a finite congruence. By the Kleene theorem $L$ is accepted by a finite automaton iff it ...
- 3,110
2
votes
0
answers
110
views
Is any CFL intersection,union of CFLs that are not inherently ambiguous?
Is any CFL intersection,union of CFLs that are not inherently ambiguous?
- 3,084
2
votes
1
answer
435
views
Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)
Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free ...
- 143
1
vote
3
answers
301
views
Is there an recursively axiomatized system with infinitely many proofs for some propositions or a proposition [closed]
Is there any recursively axiomized system with infinitely many proofs for some propositions or a proposition? So we will have at least one proposition which is deduced from the recursively axiomatic ...
- 3,084
1
vote
3
answers
2k
views
A polynomial-time algorithm for deciding whether a language has a polynomial time algorithm
Let $L$ be a language in $NP$. Then are there any results on whether there exists a polynomial-time algorithm (polynomial in the length of the description of $L$) to decide whether $L \in P$? Are ...
- 601
1
vote
4
answers
3k
views
A subset of all languages which is uncountable?
Maybe I'm being dense here, but can someone give me a subset of the set of all languages which is uncountable and the subset is easy to describe? (Some natural subset -- not like "take the set of all ...
- 2,416
1
vote
2
answers
480
views
Satisfiability problem for FOL[<,R]
Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say:
< is a strict partial order and R is an irreflexive and ...
- 105
1
vote
4
answers
16k
views
REGULAR TM is undecidable [closed]
I'm sure you all are familiar with Theorem 5.3 from Sipser's TOC book:
S = "On input (M,w) where M is a TM and w is a string:
1. Construct the code of TM M2 as follows:
M2 = "On input x:
(a) If x = ...
- 21
1
vote
3
answers
576
views
Graph properties: definability and decidability
[This is a side question to Supervenience in mathematics.]
There are graph properties that are not FO-definable, but MSO-, TC-, or LFP-definable. There may be other graph properties that are not MSO-,...
- 9,720
1
vote
1
answer
772
views
Is there any danger far from home? (Edited & Revised Version) [closed]
The notion of formal proof is defined by finite sequences ($<\omega$ - sequences) of sentences. In some sense if a sentence $\sigma$ is (finitely) provable from the theory $T$ it is very "near" to ...
user42090
1
vote
1
answer
260
views
The automorphism groups of smallest grammars of a language string are isomorphic
Let $s \in \Sigma^*$ be a formal language string. Consider the automorphism group of $s$, defined to be the set of all permutations of positions of $s$ that leave $s$ fixed. For instance $G(abab) = \...
- 260
1
vote
2
answers
2k
views
Translate a buchi automaton to LTL
How can I translate a Büchi automaton A to LTL(linear temporal logic) if $L(A)$ is definable in the LTL?
MY idea is : Büchi automaton $A$ ===> QPTL ===> LTL
I know that given any Buchi ...
- 73
1
vote
1
answer
171
views
Terminology for set of infinite strings with a certain prefix
Let $\mathcal{A}$ be a finite alphabet, and let $C$ be the Cantor space $\mathcal{A}^\omega$ under the product topology.
Given a finite string $s \in \mathcal{A}^*$, let $C(s)$ be the set of all ...
- 8,483
1
vote
1
answer
260
views
The intersection of Block Groups and R-trivial (finite) monoids
Let $\textbf{BG}$ be the pseudovariety of block groups, also known as $\textbf{EJ}, \textbf{PG},\ldots,\text{etc.}$(see [1]), and let $\textbf{R}$ be the pseudovariety of R-trivial monoids, by the ...
- 424
1
vote
1
answer
161
views
Errors in Waksman's Solution to Cellular Automaton Firing Squad Problem?
Recently, a student and I have been working through Waksman's paper ``An Optimum Solution to the Firing Squad Synchronization Problem.'' The paper claims that for any value of $n$, the proposed ...
- 413
1
vote
1
answer
158
views
On the boundedness of linear representations of formal power series of languages.
Let $\Sigma$ be a finite non-empty set of symbols (i.e. an alphabet). Fix $\pi, \eta\in\mathbb{R}^{1\times m}$ and for every $\sigma\in\Sigma $ fix $A(\sigma)\in\mathbb{R}^{m\times m}$.
We also ...
- 424
1
vote
1
answer
311
views
Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?
Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}?
One case this is possible is when ...
- 454
1
vote
0
answers
95
views
Determine equivalences in the generated collection of subgroups and quotients
Let $A$ be an abelian group, and $B_1, B_2, \dots, B_m$ be subgroups of $A$. Define the family of subgroups $\mathcal{D}_0 = \{ \{0\}, A, B_1, B_2, \dots, B_m \}$.
Let $\mathcal{C}_1$ be the ...
- 807
1
vote
0
answers
62
views
The set of closed untyped $\lambda$-terms is not context-free?
The set of untyped $\lambda$-terms is obviously context-free. But, according to Barendregt's paper Discriminating coded lambda terms (six lines before Theorem 1.5), the set of closed untyped $\lambda$...
- 1,382
1
vote
0
answers
51
views
Name for a class of languages closed under union, inverse generalised sequential machine mappings and intersection with regular languages
I asked this question on the TCS stackexchange but have so far received no answer:
Is there a name for classes of languages closed under finite union, inverse generalised sequential machine mappings ...
- 373
1
vote
0
answers
206
views
Is it possible to construct a formal language that allows to refer to specific real numbers that encode ordinals accidentally writable by an ITTM?
Let $A$ denote a particular (fixed) algorithm to encode ordinals as real numbers. The exact technical description of $A$ is irrelevant for this question: it can be any algorithm that is mathematically ...
- 959
1
vote
0
answers
265
views
What does homomorphism between languages mean to the correspoding Turing Machines?
According to the article: every c.e.language over $\Sigma^*$can be formed by homomorphism from a Dyck language over $\Sigma^{'}$ intersection with a minimal linear language over $\Sigma^{'}$ to the ...
- 3,084
1
vote
0
answers
58
views
Question about link between non-terminals of grammars and variables of Diophantine equations
If we change the right arrow in the rewriting rules of grammar into equators , changes all terminals into x and keep the non-terminals unchanged,we get system of equations.In some cases,those ...
- 3,084
1
vote
0
answers
66
views
Is it possible to classify all the inequivalent classes of first order sentence with quantifier rank fixed
It is known that for symbols with finite many relations, the number of inequivalent class of first order sentence with quantifier rank $m$ is finite. But is it possible to list (classify) them? At ...
- 11
1
vote
0
answers
479
views
Comparing two metrics on the space of infinite sequences and relating open and closed sets
Let $X = \{ 0, 1 \}$ and $X^{\mathbb N_0} = \{ x_0 x_1 x_2 \ldots : x_i \in X \}$ be the space of all infinite sequences, then a metric could be defined on it
$$
d(u,v) := \frac{1}{2^r} \mbox{ with } ...
- 798
1
vote
1
answer
91
views
Simple asymptotic combinatorics - how many words are there in a certain weight category? [closed]
Given the set of all binary strings of length n, I am looking at the "middle" of these strings, weight-wise.
Namely, I am trying to calculate how many words are there whose weight is between n/2 - ...
- 19
0
votes
1
answer
187
views
Can decidability results for monadic second-order logic be extended to monadic higher-order logics?
Call a higher-order logic fully monadic if and only if all of its predicate constants (at any order) and higher-order variables (at any order) are monadic (and it has no function symbols). In /...
- 1
0
votes
1
answer
280
views
What is the conditional probability or probablity of classes of languages?
What is the conditional probability or probability of classes of languages?
Let $E,C,S,F,R $ be the class of computably enumerable languages,computable languagesl,context-sensitive anguages,context-...
- 3,084
0
votes
1
answer
208
views
Does the fixed point lemma / diagonalization require capturing or not?
Peter Smith's formulation of the diagonalization lemma is essentially as follows, from Theorem 47 of his (fantastic) online book:
If theory T extends Robinson Arithmetic, and P is an one-place open
...
- 31
0
votes
1
answer
185
views
Building optimal rewriting rules.
Please give me some pointers where I can learn more about the following problem:
I have two alphabets A and B. A have a dictionary which contains words in A together with their translation in B (ie. ...
- 173
0
votes
1
answer
158
views
any given c.e.set has number M whose power bounds the corresponding elements of S?
For S ,any given c.e.set,does there exist a M (integer) and a partially computable function outputing every element of S the c.e.set ,such that $\forall x\in S,\exists n x=f(n)$ and $x=f(n)\leq ...
- 3,084
0
votes
0
answers
113
views
Empty context-sensitive language independent of ZFC?
Is there a simple context-sensitive grammar $G$ such that $L(G)=\emptyset$ is independent of ZFC?
$L(G)$ is the formal language generated by $G$.
- 11
0
votes
0
answers
74
views
Transformation or correspondence between language and real number
As we know, formal language can be regarded as a set of strings of alphabet, and real number can be regarded as sequence generated by set of integers, for example, denominators of the simple continued ...
- 3,084
0
votes
0
answers
197
views
Is the positive existential theory undecidable?
Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ?
How can we prove the (...
- 309
0
votes
0
answers
105
views
Counting path generating sentences in a specific formal language
Given a formal grammar of a language or an Turing machine of the language, can we count the path that generating sentences of the language?
For example, we know that if the grammar is context-free ...
- 3,084
0
votes
0
answers
70
views
Two sets of strings resulted from a set represented by binary and decimal code are in the same class of languages?
Two sets of strings resulted from a set represented by binary and decimal code are in the same class of languages as regular languages,context-free languages,context-sentive languages ,computable ...
- 3,084