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.
1
vote
0answers
122 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 ...
8
votes
4answers
769 views
Formalizations of the idea that something is a function of something else?
I'll state my questions upfront and attempt to motivate/explain them afterwards.
Q1: Is there a direct way of expressing the relation "$y$ is a function of $x$" inside set theory?
More ...
1
vote
1answer
125 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 ...
2
votes
1answer
46 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 ...
15
votes
3answers
576 views
Representing mathematical statements as SAT instances
The following problem (call it THEOREMS) belongs to class NP.
Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary.
Output: "Yes" if ...
4
votes
0answers
157 views
How can I catalog these generalized Collatz problems?
The Collatz conjecture can be expressed in terms of a ruleset in the language $\{x,+,1,\rightarrow,;\}$:
$x + x + 1 \rightarrow x+x+x+1+1;$
$x + x \rightarrow x;$
Whenever a number matches ...
0
votes
0answers
65 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 ...
1
vote
0answers
84 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 ...
1
vote
1answer
115 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 ...
7
votes
1answer
276 views
Can ETCC/ETCS talk about 'size issues'?
In material set theories (like ZFC), one can prove that there is no set of all sets. Can one prove a similar statement in ETCS? This exact statement "there is no set x such that y in x for every set y"...
2
votes
2answers
187 views
Topology induced by context-free language
Is there any way to reasonably define a topology on a context-free-language language? In other words, given a context-free grammar (or perhaps a grammar from an interesting subclass of context-free ...
5
votes
2answers
676 views
What exactly is a judgement?
Before formulating my question, let me briefly sum up what I know about the topic (feel free to correct me if something I claimed is false!). This is for you good to see what my state of knowledge is, ...
5
votes
1answer
340 views
What do we call this quantifier (“binder”)?
There's a quantifier ("binder", whatever), call it $\alpha$, defined as follows: $\alpha x.\tau$ is the (usually infinite) expression obtained by applying the substitution $\{x \mapsto \tau\}$ to the ...
6
votes
2answers
268 views
Neighbourhood of a word and Levenshtein distance
The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of insertions,...
10
votes
0answers
341 views
Computing the ordinal of a rational language well-partially-ordered by the subword relation
Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by ...
12
votes
0answers
215 views
Reference request: exponential growth rates of subword-closed languages are integers
For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters. The ...
9
votes
1answer
452 views
Coherence and rewriting
In category theory there are numerous coherence theorems (https://ncatlab.org/nlab/show/coherence+theorem). One example is the Mac Lane's coherence theorem for monoidal categories. This and probably ...
3
votes
1answer
392 views
How to get $\omega$-regular expression from buchi automaton
Is there an algorithm or a trick on how to get $\omega$-regular expressions from Buchi automatons? If yes, is there also some way to do create minimal such regular expressions?
It is extremely ...
-2
votes
1answer
245 views
Deterministic Finite Automata question [closed]
I am very new to finite automata, and I came across an issue in my professors lecture slides which I think is wrong, and I'd wonder if any of you could confirm:
Alphabet: {1}
Automata
Surely the ...
0
votes
0answers
174 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 (...
6
votes
1answer
393 views
Show that the positive existential theory is undecidable
To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: $...
0
votes
0answers
169 views
Probability of substring given string production probabilities
I originally posted this question on the Math StackExchange, but have not received answers there and thought it might be more appropriate to post it here.
Let $\Sigma$ be an alphabet and let $y = x_1 ...
1
vote
0answers
38 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 ...
1
vote
1answer
93 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 ...
1
vote
1answer
185 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) = \...
9
votes
0answers
136 views
Is there a ``Ladner's Theorem" for the PH-vs-PSPACE scenario?
Like a statement of the kind, ``If the Polynomial Hierarchy (PH) $\neq$ PSPACE then there exists $L \in PSPACE \backslash PH$ which is not PSPACE-complete"?
Or is there something else that states ...
6
votes
2answers
178 views
Is this variant of the balanced bracket language context free?
Consider the language generated by the following context free grammar:
$$
S \to SS \quad S \to () \quad S \to (S) \quad S \to [] \quad S \to [S]
$$
There is a one-to-one correspondence between this ...
0
votes
0answers
95 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 ...
6
votes
2answers
188 views
Formal languages with non-unique interpretations of terms
In mathematical logic and model theory, one considers interpretations of syntactic expressions: terms without free variables are interpreted as elements of some structure, formulas without free ...
3
votes
3answers
162 views
Are there any results on well-quasi-ordering of languages?
There are a number of papers that I can find about well-quasi-orders in formal lnaguage theory, by Kunc, de Luca, D'Alessandro, and Varricchio, among others. I am interested, however, in well-quasi ...
4
votes
2answers
627 views
Inherent ambiguity of the context-sensitive language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j} $ or $a^nb^nc^nd^ne^nf^n$
What is the definition of ambiguity of context-sensitive
grammar?This is relevant to the definition of inherent ambiguity of
context-sensitive language.And any proof for the inherent ambiguity of ...
7
votes
1answer
367 views
Is there a name for infinite words containing every finite words?
Apparently, the closest thing I've found would be normal number http://mathworld.wolfram.com/NormalNumber.html
But requiring that every finite words occurs is weaker than this property. So I'm ...
1
vote
0answers
48 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 ...
1
vote
0answers
60 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 ...
0
votes
0answers
66 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
votes
0answers
450 views
Complexity of counting words of given length in regular or context-free language
Let $L$ be a regular or context-free language over
alphabet $\{0,1\}$.
What is the complexity of counting words of length $n$ in $L$?
Is it possible to efficiently find if for given $n$
all words ...
1
vote
0answers
189 views
Examples of languages that are in P and are not in CFL [closed]
Any examples of languages that are in P(polynomial time to recognize it) and are not in CFL(context-free language)?The more the better.
16
votes
1answer
1k views
Is there an unambiguous CFL whose complement is not context-free?
I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...
5
votes
1answer
381 views
Expressive power of first-order category theory
Given the signature $\lbrace \mathsf{dom}, \mathsf{cod}, \mathsf{id},\circ \rbrace$ and the axioms of category theory – which are expressible in the signature's first-order (FO) language – ...
2
votes
2answers
284 views
Every infinite c.e.language is infinite or finite union of regular languages including at least one infinite regular language?
Is Every infinite c.e.language infinite or finite union of regular languages including at least one infinite regular language?
And is every infinite c.e.language that is not indexed language(that may ...
6
votes
1answer
140 views
Separating infinite words sharing factors by automata
Two infinite words $\xi, \eta \in X^{\omega}$ are separated by an (Büchi-)automaton if it accepts one but not the other.
Denote by $F_n(\xi)$ the factors of length $n$ of an infinite word $\xi$ and ...
6
votes
1answer
104 views
Generalising the adherence operator and its closure properties with regard to regular (rational) languages
Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some Büchi-...
2
votes
1answer
134 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[...
5
votes
1answer
235 views
What prefix and factors determine a ultimately periodic word uniquely
Let $\xi$ be an ultimately periodic sequence, i.e. there exists finite sequences $p, q \in X^*$ such that $\xi = pq^{\omega}$. Does there exists a $n > 0$ such that the prefix of length $n$ and all ...
0
votes
1answer
745 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 ...
0
votes
0answers
125 views
Proof of conjecture that permutation-free automata restrict the possible states visitable from a stringset sharing prefixes and infixes
An automaton $\mathcal A = (X, Q, \delta, q_0)$ is called permutation-free iff no word $w \in X^*$ induces a nontrivial permutation of a subset of the states of $\mathcal A$. More formally for any $R \...
1
vote
0answers
348 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 } ...
3
votes
0answers
144 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 ...
5
votes
2answers
329 views
Concatenation of strings [closed]
We have two strings (i. e., finite tuples) $A$ and $B$.
We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...
3
votes
1answer
144 views
Subsets of $\omega$-regular lanuages accepted by automata with special acceptance condition
Let $\mathcal A = (X, Q, \delta, q_0, F)$ be a deterministic finite automata with the following acceptance condition on infinite words:
The automata accepts $\xi \in X^{\omega}$ with respect to $F$ ...
