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

formal languages, grammars, automata theory

-2
votes
0answers
50 views

$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$ [closed]

$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$ My solution: We can have $Tyes$ for $Σ^*$ and $Tno$ for $ϕ$. Hence, $L_1$ is no ...
-3
votes
0answers
40 views

Is the complement of an unambiguous context-free language (UCFL) context-free? [closed]

The question is entirely in the title. Expanding it a bit, it reads as follows: Given a context-free grammar (CFG) with the promise that it recognises a UCFL, does there exist a CFG for its complement?...
6
votes
0answers
58 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
92 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
51 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
41 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
96 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
114 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 $...
1
vote
1answer
159 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 ...
6
votes
1answer
153 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
27 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
65 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
vote
0answers
89 views

Possibly small circuit complexity class containing REG?

What is the smallest well-known Boolean-circuit complexity class containing all the regular languages over the binary alphabet {0,1}? If we believe Theorem 2 in Koucký, Circuit Complexity of ...
3
votes
1answer
146 views

Converting Kuroda normal form rules to the Penttonen normal form

Let us say we have some abstract context-sensitive grammar in the Kuroda normal form, which is where all production rules are of the form: $AB\rightarrow CD$ or $A\rightarrow BC$ or $A\rightarrow B$...
4
votes
1answer
186 views

What is the complexity of counting parse trees?

A Counting Problem Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$? An Example Instance Let's consider an example instance consisting of a CFG $G$ with ...
4
votes
1answer
196 views

Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

$CFL$ is the class of context-free languages. Question Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $DCFL$?
9
votes
0answers
105 views

Deterministic context-free languages that can be represented as the word problem of a group

Consider a group $G$. We call $G$ virtually free is it contains a free subgroup of finite index. If $G$ is finitely generated by some set $X \subseteq G$ one can consider the word problem $WP(G)$ ...
2
votes
1answer
58 views

Looking for a particular normal form for Context-sensitive grammar

I am wondering if there is a described normal form for Context-sensitive grammar, which is something similar to Kuroda normal form and Greibach normal form. That is to say, each rule in such form ...
3
votes
1answer
64 views

Generalizing Parsing Expression Grammar for Context Sensitive Grammars

One of the things I like about parsing expression grammars is that they're automatically unambiguous, and unambiguity is a very important property to have. However, context-free grammars are somewhat ...
0
votes
1answer
129 views

Visualizing the parse structure of a range concatenation grammar

The above is a good visualization of a derivation for a specific sentence in a context free language. You can find many more on Google Images by searching "context free grammar." Let's consider the ...
6
votes
1answer
114 views

Is this generalization of context free grammars known and strict?

Let $\Sigma$ be an finite alphabet and $(N, \circ)$ a semigroup. The semigroup operation on $N$ can be extended to $\mathscr{P}(N)$: $N_1 \circ N_2 := \{ \; n_1 \circ n_2 \; | \; n_1 \in N_1, \; n_2 \...
2
votes
0answers
35 views

A class of languages admitted by a class of grammars equivalent to $\mathbf{PR}$?

Is there a class of languages $L(G)$ admitted by a class of phrase structure grammars $G$ equivalent to $\mathbf{PR}$? (the class of primitive recursive languages = $\mathbf{LOOP}$)? In greater ...
2
votes
1answer
82 views

Is there a name for this property of a term rewriting system?

Given TRS let's call it top-reducible or left-reducible if no rule's right hand side is contained in any rule's left hand side non-trivially. A term A is contained in an other one B trivially if ...
4
votes
0answers
156 views

“Context” understanding in tree grammars

The Context-Free tree grammar has rules of the form: $A\rightarrow t$ or $A(x_1,\dots,x_n)\rightarrow t_x$, where $A\in N$, $t\in T(N\cup T)$, $t_x\in T(N\cup T\cup \{x_1,\dots,x_n\})$, $T(Z)$ ...
0
votes
0answers
100 views

Is it possible to transform a theory written in FOL into an equivalent theory that uses conditional equational logic plus Boolean Algebra?

I am studying the relationship between First Order Logic (FOL) specification methods (e.g. CASL) and equational based specification (e.g. CafeOBJ). My question is: Is it generally possible to ...
7
votes
3answers
239 views

What are graph grammars?

I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview ...
1
vote
0answers
72 views

What logic(s) exist for attributing belief?

I'm looking for an appropriate formalism to represent "traceability" in claims, especially connecting conclusions to source materials in a rigorous way. For example, I'd like to be able to represent ...
-1
votes
1answer
75 views

What is the relation between P-immune languages and NP-complete languages? [closed]

Can a NP-complete language be P-immune? Why can't existence of P-immune languages separate NP from P?
1
vote
1answer
96 views

Set of languages that can represent every c. e. languange

Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e....
-1
votes
1answer
69 views

Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?

Is there inherently ambiguous language which can not be recognized by Deterministic LBA? For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?
5
votes
1answer
156 views

What is the motivation behind defining Deterministic Looping Automata?

I was wondering about what could possibly be the motivation behind defining the deterministic looping automata? What puzzles me is that they accept a word iff they have a run on it! I believe they ...
1
vote
2answers
107 views

Determine if a structure is a model of an inductively defined predicate

My setting is first-order logic. As an example, consider an inductive definition of a linked list: $List(l)$ = $Null(l)$ $\vee~(Node(l) \wedge \exists sublist. List(sublist) \wedge next(l,...
3
votes
1answer
216 views

NFA to 2DFA: what are the upper and lower bounds?

Suppose that one has an NFA (from, say, a regular expression). What is the state complexity of turning it into a 2DFA?
3
votes
1answer
66 views

Reference: Cancellability of the Dyck congruence

I consider the Dyck congruence $\equiv$ on a parenthesis alphabet $\Sigma = \{a, \bar a, b, \bar b\}$, i.e. the least congruence on $\Sigma^*$ such that $a \bar a \equiv \varepsilon $ and $b \bar b \...
1
vote
0answers
26 views

Range concatenation grammars which are unambiguous as (and are NOT CFL)?

Are there any range concatenation grammars that generate only one possible parse tree are not also context-free?
1
vote
0answers
54 views

Relation between MDPs and non-deterministic finite automatons

I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus ...
18
votes
1answer
415 views

Is equivalence of unambiguous context-free languages decidable?

It is well known that the equivalence problem is undecidable for general context-free languages. However, all proofs of this fact that I am aware of seem to involve some ambiguous context-free ...
2
votes
0answers
68 views

Is there a DCSL that cannot be recognized in O(n^2) steps by a deterministic LBA?

Is there a context sensitive language $L$ so that $L$ cannot be recognized by a deterministic linear bounded turing machine in $O(n^2)$ steps, but still can be recognized by a deterministic LBA? The ...
1
vote
0answers
57 views

If for every non-terminal in a cs-grammar there exists an obligatory rule, does this alter the language of derivable strings

I am reading Chomsky's article Three models for the description of language, one of the earliest papers where context-free and context-sensitive grammars are mentioned. Essentially what he calls ...
7
votes
0answers
170 views

Reference request: exponential growth rates of subsequence-closed languages are integers

This question is migrated from MathOverflow, where it did not receive any answers a year ago. For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $...
20
votes
0answers
508 views

Why is the Pumping Lemma sometimes called Bar-Hillel's Lemma?

There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, here, here, and on the Wikipedia page). However, the first ...
3
votes
1answer
79 views

Giving a finite collection of infinite words “complex” enough with respect to automata measure

We consider acceptance by Büchi automata. Let $X = \{0,1\}$ and $X^{\mathbb N}$ the set of all infinite sequences. Then for each $n$ do we have a finite collection $\{ \xi_1, \xi_2, \ldots, \xi_k \}$ ...
2
votes
1answer
70 views

Regularity of language with finite number of right derivatives

I found this statement listed as a theorem in a textbook: If L ⊆ Σ∗ is any language, then L is regular iff it has finitely many right derivatives. Furthermore, if L is regular, then all its right ...
4
votes
0answers
112 views

Justifying the state of virtual memory as a vector space

First, I'm mostly experienced with Math, which I hope won't be too inconvenient. I saw Operational Calculus on Programming Spaces by Sajovic and Vuk, which seemed very interesting to me (for a "short ...
7
votes
1answer
302 views

Where does the “intuitive” understanding of Kolmogorov complexity fails

Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example on wikipedia. So to give this more formal meaning, define $$ K'(x) := ...
3
votes
2answers
126 views

Construct proof systems for common algorithmic task, like equivalence of regular expressions

A propositional proof system according to Cook and Reckhow for a language $L \subseteq \Sigma^{\ast}$ is a deterministic polynomial time function $f : \Sigma^{\ast} \to L$ that is onto. For $y \in L$ ...
6
votes
0answers
84 views

Salomaa's axiomatisation of regular languages and the use of regular expression in it

I am reading the classical article of A. Salomaa where he gives two axiom systems for regular sets and proofs consistency and completeness. As I have understood it, an axiomatic system in some logic (...
4
votes
1answer
94 views

Place of tree-adjoining grammars in the hierarchy of tree grammars

As tree-adjoining grammars operate with trees, I suppose they can be considered as a kind of tree grammars. If this assumption is correct, I'm wondering: where should we place them in the tree grammar ...
6
votes
2answers
321 views

In the context of regular languages, must the alphabet be finite?

In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all ...
7
votes
1answer
109 views

Class of languages accepted by Python RegEx?

Python / Java / Perl / Ruby / etc. extend regular expressions to permit look-ahead and look-behind, e.g., LookAround: (?=...) (?<=...) (?!...) (?<!...) I ...