Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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$ ...