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
280
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 ...
- 7
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
6
votes
1
answer
485
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: $...
- 309
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
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 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
9
votes
0
answers
221
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 ...
- 1,893
7
votes
2
answers
216
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 ...
- 3,830
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
5
votes
2
answers
266
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 ...
- 1,481
4
votes
3
answers
227
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 ...
- 141
6
votes
2
answers
1k
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 ...
- 3,084
9
votes
1
answer
443
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 ...
- 93
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
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
6
votes
1
answer
949
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 ...
- 25.4k
17
votes
1
answer
2k
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 ...
- 1,173
5
votes
1
answer
592
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 – ...
- 9,720
2
votes
2
answers
622
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 ...
- 3,084
6
votes
1
answer
165
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 ...
- 798
6
votes
1
answer
135
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-...
- 798
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
5
votes
1
answer
346
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 ...
- 798
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
0
votes
0
answers
154
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 \...
- 798
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
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
5
votes
2
answers
387
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 ...
- 59
4
votes
1
answer
172
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$ ...
- 798
5
votes
2
answers
245
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?
- 1,437
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
4
votes
1
answer
191
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 ...
- 424
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
4
votes
1
answer
322
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 ...
- 841
2
votes
2
answers
251
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 ...
- 3,084
7
votes
1
answer
548
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 ...
- 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
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
0
votes
0
answers
780
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 ...
- 3,084
6
votes
1
answer
955
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 ...
- 3,084
20
votes
2
answers
734
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 ...
- 371
3
votes
3
answers
5k
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 ...
- 87
-1
votes
2
answers
2k
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?
- 3,084
5
votes
1
answer
673
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 $$L=\{a^nb^...
- 3,084
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
4
votes
0
answers
125
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) \...
- 73
12
votes
5
answers
3k
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 $P(...
user6976
-1
votes
1
answer
7k
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
- 9
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