Questions tagged [fl.formal-languages]

formal languages, grammars, automata theory

Filter by
Sorted by
Tagged with
4
votes
3answers
247 views

Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as Extended Church-Turing Thesis real-life quantum stuff is even given ...
1
vote
1answer
65 views

How to prove that Supremum preorder coincides with Hoare preorder?

Given a complete lattice $(L, \sqsubseteq)$ and a basis of completely $\sqcup$-irreducibles $B_L \subseteq L$, such that $\forall l \in L$, $l=\sqcup\{b \in B_L\ |\ b \sqsubseteq l\}$. I mean: Hoare ...
5
votes
1answer
134 views

Kolmogorov Complexity of a Decidable Language

The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable ...
6
votes
2answers
158 views

2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ? I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in ...
5
votes
0answers
114 views

Languages whose Parikh image is recognizable

Let $\Sigma$ be some alphabet, and $p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$ the Parikh map. A formal language $L \subseteq \Sigma^*$ is called a slip-language, if $p(L)$ is a semilinear set. By ...
2
votes
0answers
67 views

Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? // Quantum automata

While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More ...
7
votes
5answers
404 views

NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
0
votes
0answers
30 views

Name for family of language classes closed under union, inverse gsm mapping and intersection with regular

Is there a name for language classes closed under union, inverse gsm mappings and intersection with regular languages? This is a bit similar to trio or AFL, but I specifically do not want to require ...
3
votes
1answer
100 views

Embarrassingly Parallel: Formal Definition & Citation

I've been unable to find a good answer for this question: Formally, what makes a problem embarrassingly parallel? Intuitively, it would seem to me that an embarrassingly parallel problem is one where: ...
10
votes
3answers
439 views

Maximum shortest word accepted by pushdown automata

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
3
votes
0answers
84 views

The number of words of length $n$ in a context-sensitive language

Let $L$ be a context-sensitive language, $s_{L}(n)$ is denoted by the number of words of length $n$ in $L$. What is known about $s_{L}(n)$? Note that it is known that $s_{L}(n)$ is either polynomial,...
3
votes
1answer
101 views

Term for a set that is not immune

At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and ...
0
votes
2answers
158 views

Is the decidability of a language decidable? [closed]

Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language? Comments + answer say trivially the answer is yes; however, I'm wondering here would ...
1
vote
3answers
348 views

what is a model of computation, mathematically? [closed]

Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't ...
0
votes
0answers
48 views

Incompleteness and term extraction

Is there a formalization, which from a proof that a system includes enough arithmetic extracts an arithmetic sentence in the language of PA, which is not provable in the given system? Imagine the ...
0
votes
0answers
58 views

Information theory for Mathematical Physics [duplicate]

What are some good introductory texts on information theory for someone who is classically trained in mathematical physics? Unfortunately my abilities in computer sciences and formal logic are next ...
-1
votes
1answer
61 views

Chomsky-Schutzenberg Hierarchies explained for physicist (general) [closed]

I am classically trained in physics, however I have been interested in the use of information theory in studying some classical systems. As someone who is somewhat unfamiliar with the language of ...
-1
votes
1answer
101 views

Ordered Grammar in THEORY OF COMPUTATION [closed]

What is ordered grammar in the theory of computation?
10
votes
1answer
212 views

What class of languages is recognized by finite-state automata with $k$ heads?

A DFA or NFA reads through an input string with a single head, moving left-to-right. It seems natural to wonder about finite-state machines that have multiple heads, each of which moves through the ...
1
vote
1answer
129 views

How are safety/liveness languages defined on the set of finite or infinite words?

Let $Σ$ be an alphabet (e.g., the powerset of atomic propositions coming from some Kripke structure, though such details are irrelevant here). For infinite words, a language $P\subseteq Σ^ω$ is ...
-1
votes
1answer
127 views

Gödel-Numbering of the Context-Sensitive Languages

I would like to have a Gödel-numbering of the context-sensitive languages. Because there is no obvious syntactic distinction between LBAs and TMs, I cannot number the former in an immediate way. So I ...
5
votes
1answer
108 views

k-testable languages with non-constant k?

Let $p_t(w)$ and $s_t(w)$ denote the prefix and suffix of length $t$ of the word $w$, respectively. If $|w| < t$, then $p_t(w) = s_t(w) = w$. Furthermore, let $i_t(w)$ be the set of infixes of ...
3
votes
0answers
45 views

Extending the sequential calculus (logic over words) to allow a hierarchy of languages like the arithmetical hierarchy

Let $\Sigma$ be some finite alphabet. Then consider the logical language $\mathcal L = \{ R_a : a \in \Sigma \} \cup \{ <,= \}$ and first order formulas. For a given first order formula $\varphi$ a ...
2
votes
0answers
101 views

Notion of “quotient” or “inverse” for recognizable tree languages?

Related to my previous question but this time I have a better idea of what I'm actually asking. I'm looking at the following operation on recognizable tree languages (i.e. regular tree grammars, ...
2
votes
0answers
55 views

Regular Tree Languages are closed under quotient?

The Wikipedia page for Regular Tree Grammars notes that if $L_1$ and $L_2$ are regular tree languages, than $L_1 \setminus L_2$ is as well. However, it doesn't define this quotient operation for trees,...
17
votes
1answer
282 views

Is the Set of all Primitive Words a Prime Language?

A word $w$ is called primitive, if there is no word $v$ and $k > 1$ so that $w = v^k$. The set $Q$ of all primitive words over an alphabet $\Sigma$ is a well known language. WLOG we can choose $\...
8
votes
1answer
167 views

A conjecture related to the Cerny conjecture - counterexample/reference request

The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a ...
6
votes
1answer
164 views

Arranging letters to make a word in a regular language

Fix a regular language $L$ on the alphabet $\{a, b\}$, and consider the following problem. I am given as input: some number $m \in \mathbb{N}$ of copies of the letter $a$, and some number $n \in \...
1
vote
0answers
33 views

Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?

I know that, for a grammar $G$ to belong to $LL(1)$, it is necessary that $G$ is not ambiguous; that is, every sentence has a unique parse tree in $G$. $G$ has no left recursion; that is, we can't ...
13
votes
1answer
262 views

Is { ww' | HamDist(w,w')>1 } context-free?

After reading the recent question "Is the complement of $\{ www \mid ...\}$ context-free?"; I remembered a similar problem I wasn't able to disprove: Is $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|...
9
votes
3answers
425 views

Continuous mathematics and formal language theory

Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics. For example, solving the intersection non-emptiness problem for a context-free ...
5
votes
1answer
162 views

For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and ...
12
votes
3answers
416 views

Is the complement of { www | … } context-free?

It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?
6
votes
1answer
261 views

Size of complement of context-free language

Let $L$ be a context-free language, $\bar L$ be its complement and $\bar L_n$ be the length $n$ words in $\bar L_n$. What is known about $|\bar L_n|$? Note that it is known that $|L_n|$ is either ...
0
votes
1answer
89 views

Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?

I've learned from several sources that an LL(1) grammar is: unambiguous, not left-recursive, and, deterministic (left-factorized). What I can't fully understand is why the above is true for any LL(1)...
11
votes
2answers
394 views

Does a given regular language contain an infinite prefix-free subset?

A set of words over a finite alphabet is prefix-free if there are no two distinct words where one is a prefix of the other. The question is: What is the complexity of checking whether a regular ...
10
votes
0answers
111 views

Are there cascade decompositions of machines that are more general than finite automata?

The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an ...
9
votes
1answer
108 views

Is there a method for proving non-regularity of string transformations?

There are a number of different models for defining transformations between languages. Finite state transducers and MSO-definable graph transformations over string graphs are the two that I am best ...
20
votes
1answer
1k views

Number of words of length n in a context-free language

Denote by $w_n$ the number of words of length $n$ in a (possibly ambiguous) context-free language. What is known about $w_n$? I'm sure this has been studied a lot, but I couldn't find anything at ...
14
votes
4answers
567 views

Base-k representations of the co-domain of a polynomial - is it context-free?

In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open: Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for ...
6
votes
0answers
82 views

Reference request: transforming a grammar to Greibach normal form preserves the number of parse trees

I believe that most "natural" ways of transforming a grammar to the GNF should preserve the number of parse trees for each string. For example, Urbanek's construction from the paper "On Greibach ...
-1
votes
1answer
282 views

What is the practical importance of making or using a Turing complete language? [closed]

I get what a Turing machine is and what language is a Turing-complete language but when someone introduces me to a new programming language (like Solidity) and says it is Turing complete, what am I ...
1
vote
0answers
62 views

Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part

Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ ...
1
vote
0answers
56 views

What is the interpretation of an infinite formal context-free grammar?

Let $L$ be a language as follows: $$ \begin{align*} L &::= a\ |\ L^{*}\\ \end{align*} $$ Now, suppose I apply some sort of transformation $T : N \rightarrow N$ where $N$ is the set of non-...
3
votes
3answers
116 views

Example of monoid $M$ such that $\operatorname{RAT}(M) \not\subseteq \operatorname{REC}(M)$

Let $M$ be a monoid, the family of rational sets $\operatorname{RAT}(M)$ is defined as the smallest set containing the finite subsets, and closed under union, concatentaion and the star operation. The ...
9
votes
1answer
159 views

Generalisation of the statement that a monoid recognizes language iff syntactic monoid divides monoid

Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $...
4
votes
1answer
542 views

How to start learning formal language theory

I sincerely apologize if this is not appropriate in this stack Q&A, though it seemed the most fitting. I want to learn formal language theory, as well as generating grammars etc. The purpose is ...
7
votes
1answer
209 views

Finding a minimal DFA whose language has a desired intersection with another

Suppose I have regular languages $B \subseteq A$, with corresponding (known) minimal deterministic finite automata $M_A, M_B$. I would like to find another regular language $C$ such that $B = A \cap ...
1
vote
0answers
31 views

Inductive definition of language operators like the set of all permutations of a word came from the shuffle operator

Let $X$ be a finite alphabet. Given two words $u, v \in X^{\ast}$ the shuffle operator is defined to be $$ u || v := \{ u_1 v_1 u_2 v_2 \ldots u_n v_n : 1 \le i \le n, u_i, v_i \in X^{\ast}, u = u_1 \...
1
vote
1answer
69 views

Relation between REG and NLOGTIME?

What is known about the relation between the class of regular lanuages and NLOGTIME? Is any class contained in another one? You have some choice of how to define NLOGTIME to get one or both ...

1
2 3 4 5
8