The formal-languages tag has no wiki summary.

**1**

vote

**0**answers

16 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

**1**answer

67 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

**1**answer

95 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) = ...

**6**

votes

**0**answers

88 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

**2**answers

138 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

**0**answers

79 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

**2**answers

180 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

**3**answers

119 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

**2**answers

343 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

**1**answer

315 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

**0**answers

43 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

**0**answers

54 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

**0**answers

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

**2**

votes

**0**answers

123 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

**0**answers

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

**13**

votes

**1**answer

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

**2**

votes

**1**answer

273 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 – ...

**1**

vote

**1**answer

132 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

**1**answer

129 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

**1**answer

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

**2**

votes

**1**answer

115 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) = ...

**5**

votes

**1**answer

143 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

**1**answer

684 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

**0**answers

86 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

**0**answers

197 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

**0**answers

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

**4**

votes

**2**answers

277 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

**1**answer

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

**5**

votes

**2**answers

187 views

### Ordering on words

What are the known computation-friendly well-orderings on words from $A^*$, where $A$ is a finite alphabet, except the standard weightlex and syllable-order?

**2**

votes

**1**answer

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

**4**

votes

**1**answer

144 views

### Progress on group languages characterizations

Def. A group language is a recognizable language whose syntactic monoid is a group.
q1. Is it known a "nice" combinatorial characterization of group languages ?
q1.1. If no, is it well understood ...

**2**

votes

**1**answer

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

**5**

votes

**1**answer

192 views

### Is it decidable whether the support of a rational $\mathbb{Z}$-series is a regular language?

Let $S \in \mathbb{Z}\langle\langle A\rangle\rangle$ be a rational series in noncommutative variables. The support of $S$ is the set of all words $u \in A^*$ such that $(S, u) \not= 0$. It is ...

**2**

votes

**2**answers

182 views

### Generating function of factorable binary words

A word $w$ on the alphabet $A := \{0, 1\}$ is factorable if
\begin{equation}
w = u^k \mbox{ where } u \in A^* \mbox{ and } k \geq 2.
\end{equation}
Let $L$ be the language of the set of ...

**7**

votes

**1**answer

334 views

### Constructing Metrics for specific Topological Spaces, and Refinements of the Cantor-Space in particular

I have a Problem in general, given some some Topological Space $(X, \tau)$ from which I know it is metrisable, how can I find a metric (that is at best in some sence constructive and easy, at the very ...

**1**

vote

**1**answer

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

**1**

vote

**3**answers

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

**0**

votes

**0**answers

302 views

### Extended definition of unambiguous language and the existence of unambiguous grammar

Let's extend the unambiguity of language and grammar as follows:
a language $L$ is unambiguous if there is a grammar that generates every word in $L$ in a unique way, the grammar may be of type 0 or ...

**5**

votes

**1**answer

522 views

### List of open problems of formal languages [closed]

As we know, there are some open problems of formal languages. I am wondering if there is a somehow complete list of open problem of formal languages. If there isn't such a list, can we make it one as ...

**20**

votes

**2**answers

590 views

### congruence on words: having the same (scattered) subwords of length at most n

For a fixed finite alphabet $A=\{a,b,...\}$, write $x \sim_n y$ if the two words $x$ and $y$ have the same (scattered) subwords of length at most $n$. The relation $\sim_n$ is a congruence of finite ...

**3**

votes

**3**answers

916 views

### L-systems and Sierpinski Triangle

I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in the picture below).
I'm interested to know how could one arrange the rules of ...

**-1**

votes

**2**answers

534 views

### Any grammar for the language $L =a^p$, $p$ is prime number of $\mathbb{N}$

Any grammar for the language
$$L =a^p,\text{ $p$ is prime and }p\in \mathbb{N}?$$
Is such a grammar related to any question of number theory like RH or the conjecture of twin primes?

**5**

votes

**1**answer

452 views

### How to work out a grammar if we know the language?

How could we work out a grammar if we know the language? How could we work out a grammar if we know the language that is restricted to a special kind like CFL or CSL? For example, we know ...

**2**

votes

**0**answers

62 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?

**4**

votes

**0**answers

97 views

### Properties of classical automata preserved in Büchi automata

Given two NFW $A$ and $B$, we regarded $A$ and $B$ as Büchi automata.
We can show that the containment property is not preserved in Büchi automata. That is, we can construct a example: $L(A) ...

**7**

votes

**5**answers

762 views

### Generating function of a regular language

It is well known that the generating function of a regular language $L$, i.e. $\sum n_kz^k$ where $n_k$ is the number of words of length $k$ in $L$, is rational, i.e. a quotient of two polynomials ...

**-1**

votes

**1**answer

283 views

### prove (a+b)*=a*(ba*)* [closed]

formal language and automata theory
regular expessions
(a+b)* =a*(ba*)*
please answer
I want the proof
thank you

**0**

votes

**1**answer

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

**4**

votes

**1**answer

767 views

### Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...

**13**

votes

**1**answer

1k views

### What's the difference between ZFC+Grothendieck, ZFC+inaccessible cardinals and Tarski-Grothendieck set theory?

Say that "U" is the axiom that "For each set x, there exists a Grothendieck universe U such that x $\in$ U", where Grothendieck universes are defined in the usual way (or, if that's unclear, in this ...