Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

274 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
41 votes
0 answers
2k views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
user avatar
  • 1,841
15 votes
0 answers
271 views

Using logic to prove non-regularity of a language

A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
user avatar
  • 12.2k
13 votes
0 answers
651 views

Test whether two languages are equal, when give in algebraic form

This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
user avatar
  • 141k
8 votes
1 answer
310 views

Is unary language with polynomial power context sensitive?

I suppose that $\Sigma = \{a\}$. Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language. It ...
user avatar
  • 151
8 votes
1 answer
319 views

Is there a strictly non-deterministic one-counter language whose complement is one-counter?

Let $A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$ Clearly, $\text{Deterministic one-counter} \subseteq A$ Is it the case that $ A = \text{Deterministic one-counter}$...
user avatar
  • 1,239
7 votes
1 answer
567 views

Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?

The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}...
user avatar
6 votes
0 answers
107 views

Where did our present regex notation originate?

First question, and my apologies if it is off-topic! This question suggests to me I may not be totally off-base. Where did our present regex notation originate? I am particularly wondering how <...
user avatar
  • 161
6 votes
0 answers
283 views

Why does Non Determinism not enhance FA like it does for PDA

Both Deterministic and Non deterministic Finite Automata can recognize the same universe of regular languages. On the other hand, Deterministic Push Down Automata can only recognize a subset of ...
user avatar
  • 161
6 votes
0 answers
376 views

Capture Avoiding Substitution of multiple variables at once

In articles you often find the terminus "capture avoiding substitution" that saves the author(s) from the tedious process to re-define a recursive function -including alpha-conversion and the ...
user avatar
  • 610
6 votes
0 answers
138 views

Can the language of squares be described by a PEG?

I believe that they can't, but I couldn't find any existing framework for parsing expression grammars akin to the pumping lemma that would allow me to prove it. The language I'm talking about is $$\{...
user avatar
  • 626
6 votes
0 answers
101 views

Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
user avatar
  • 291
5 votes
0 answers
103 views

Growth function for non-regular languages

For language $L$ over an alphabet $\Sigma$ denote $\gamma_L(n)$ as the number of words of length $n$ in the language $L$. It is known that for regular languages this function represents a sequence ...
user avatar
  • 61
5 votes
0 answers
98 views

Is the set finite words over an alphabet a final coalgebra*?

I am studying what coinduction is. In particular, I am reading that coinductive datatypes can be defined as elements of a final coalgebra for a given polynomial endofunctor on $\tt Set$. I've seen ...
user avatar
  • 51
5 votes
0 answers
173 views

Weak equivalent tree grammar for Context-sensitive word grammar?

Consider arbitrary context-sensitive grammar on strings $G_s$. Is any known and described formalism (or type) for tree grammars, using which we can build weak-equivalent tree grammar $G_t$, which ...
user avatar
5 votes
0 answers
91 views

Languages recognized by finite state automata of polynomially growing size

In the course of my research (condensed matter physics stuff), I stumbled over the following concept: The class of regular languages can be defined via finite state machines (FSM): A language $L$ is ...
user avatar
  • 91
5 votes
0 answers
231 views

How to disambiguate symbolic regular expressions

What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
user avatar
  • 315
4 votes
0 answers
69 views

Reference on relating Post systems to string rewriting systems and formal grammars?

wikipedia states: Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...] It has been proved that any Post canonical system is reducible to such a ...
user avatar
  • 3,474
4 votes
0 answers
117 views

Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?

Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing? The ...
user avatar
  • 141
4 votes
0 answers
107 views

Computational power of nondeterministic type-2 min-heap automata

I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here. ...
user avatar
  • 12.6k
3 votes
0 answers
32 views

Is there an alternative for the formal language theory that could be used for flowchart diagrams?

I am creating a tool for validating, parsing and interpreting flowchart diagrams on diagrams.net, and it is neccessary to give users an opportunity to define a set of rules for the diagram. So, in the ...
user avatar
3 votes
0 answers
84 views

Hopcroft & Ullman: 1969 vs. 1979

How do the 1969 and 1979 books by Hopcroft & Ullman compare? Was the 1969 book an earlier version of the 1979 book? 1969: Formal Languages and their Relation to Automata 1979: Introduction to ...
user avatar
3 votes
0 answers
64 views

Some guess about concatenation of intersection of languages

I know this is an amateur question but is it true to say that for any three nonempty languages $L_{1},L_{2},L_{3}$ over an alphabet $\Sigma$ we have $L_{1}(L_{2} \cap L_{3}) = L_{1}L_{2} \cap L_{1}L_{...
user avatar
  • 377
3 votes
0 answers
63 views

Words of the same length in a language

Let $L\subseteq\Sigma^*$ be a language, where $\Sigma$ is a set, and let $n\in\mathbb N$. I am wondering if there is some good terminology for $L\cap\Sigma^n$. Of course I could say "the set of ...
user avatar
3 votes
0 answers
38 views

Subexponential size of string to prove $\{xy : x,y \in \{0,1\}^\star, |x| = |y|, x \ne y\}$ is not regular?

In the standard proof of this language not being regular using the Pumping Lemma for Regular languages, one picks $0^p 1^p 0^{p+p!} 1^p$ where $p$ is the pumping constant and using that can derive the ...
user avatar
  • 1,013
3 votes
0 answers
233 views

is it decidable whether a grammar in Chomsky normal form has useless rules?

Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
user avatar
  • 818
3 votes
0 answers
81 views

BNF rule to regular expression

I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression. (With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
user avatar
3 votes
0 answers
71 views

Are there context free grammars for all restricted Dyck paths?

A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...
user avatar
3 votes
0 answers
26 views

Automaton without stack for visibly pushdown languages

This paper here describes an alternating automaton which can recognize visibly pushdown langauges without using a stack. Unfortunately the transformation from NVPA to such an automaton is skipped in ...
user avatar
  • 375
3 votes
0 answers
100 views

Generating valid sentence with respect to attribute grammar

Given a context free grammar, both the algorithm for determining whether a given string is grammatical and the algorithm for producing a grammatical string in that language are well understood. To ...
user avatar
  • 213
3 votes
0 answers
58 views

Sets whose decimal expansions form a regular language

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). For a set $S$ of natural numbers, let its set of expansions (in base 10) be $\bar S = \{\bar n \...
user avatar
3 votes
0 answers
28 views

How to model grammar ambiguity

Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings. Practically, ...
user avatar
  • 321
3 votes
0 answers
127 views

Algorithms to match regular expressions containing backreferences

I'm trying to come up with an implementation of a matcher for regular expressions containing backreferences like: ([a-c])x\1 which would match ...
user avatar
3 votes
0 answers
157 views

Do Combinational Logic circuits describe a set of languages?

I was looking at this picture: https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/640px-Automata_theory.svg.png Which made me think, that if all Turing Machines PDA's and ...
user avatar
  • 367
3 votes
0 answers
84 views

Can we define CFL without grammars or automata?

The set of regular languages $R$ over an alphabet $\Sigma$ can be defined as the smallest set satisfying these 5 axioms: Empty language: $\{\} \in R$ Singleton languages: $\forall a \in \Sigma : \{a\}...
user avatar
  • 386
3 votes
0 answers
103 views

What kind of formal language is generated by Parsing Expression Grammars?

I've been unable to find what class of languages is recognized by PEGs. The original paper [1] only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also ...
user avatar
  • 31
3 votes
0 answers
55 views

Tree Languages are Word Languages on an Infinite Alphabet of Contexts

I have been reading the book Tata (Tree Automata Techniques and Applications), and there is a sentence I have read thousands of times, yet still don't quite understand. In the beginning of Chapter 2, ...
user avatar
  • 1,841
3 votes
0 answers
128 views

Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution

Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally $\...
user avatar
  • 630
2 votes
0 answers
37 views

Reading list for mathematics and formal logic with missing truth values?

I would like a reading list of math and formal logic books which give a principled discussion of missing values. Textbooks on mathematics and formal logic - propositional and first-order and higher-...
user avatar
  • 163
2 votes
0 answers
29 views

Why process algebras à la chemical abstract machine are not common?

I recently read the Berry and Boudol's chemical abstract machine [1, 2]. I found the way they describe the semantic really nice and quite intuitive for a process calculus. The aspect that really ...
user avatar
  • 121
2 votes
0 answers
34 views

Regular string relations - proof of correctness

Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows: $$ R^{obl}(T) := N(T) \cdot (T \cdot N(T))^* $$ $$ N(T) := ...
user avatar
2 votes
0 answers
86 views

Which of these languages is regular? The Pumping Lemma seems to show none are

I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular? $$ \{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
user avatar
  • 21
2 votes
0 answers
367 views

Pumping lemma for L = {a^i b^j c^k: i < j < k}

I had a question regarding a specific proof I found online that I had some concerns with, I have quoted it below. Show that the language L = {a^i b^j c^k: i < j < k} is not a context-free ...
user avatar
2 votes
0 answers
264 views

Does SLR(0), LALR(0) exists?

I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
user avatar
  • 1,547
2 votes
1 answer
2k views

How would a Turing Machine recognize n consecutive characters

I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters ...
user avatar
2 votes
0 answers
67 views

Give LL grammar for this language?

I need to give the LL grammar for the language below and explain why the grammar is LL and what the value of $k$ should be: $$L = \{ a^n c^m c^{n+m} : n \ge 1, m \ge 1 \}. $$ I have the following, ...
user avatar
  • 21
2 votes
0 answers
91 views

Looking for a subclass of deterministic context-free languages, other than the subclass of regular languages

Let $X=\{x_1,\ldots,x_n\}$ be a finite set of alphabet and $X^\ast$ denote the set of all words (including empty word) over $X$. Clearly, $X^\ast$ is a regular language. Is there a subclass, say $C$, ...
user avatar
  • 21
2 votes
0 answers
133 views

How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?

Given a context-free grammar $G$, let $\longrightarrow_G$ be the (one-step) rightmost derivation relation, and $\longrightarrow^*_G$ its reflexive and transitive closure. Let $S$ be the start symbol ...
user avatar
2 votes
0 answers
706 views

Is the complement of $L = \{a^nb^mc^p \, n= m= p\}$ context free language?

Is the complement of $L = \{a^nb^mc^p \ , n= m= p\}$ a context free language. I believe that we can write $L^{'} \ as \ L1 \cup L2$ where $L1=(a^*b^*c^*){'} \ $ $L2={{a^nb^mc^p \ m\ne n \ or \ n\...
user avatar
2 votes
0 answers
709 views

Understanding definitions of Deterministic Context Free Grammar and Deterministic Pushdown Automaata

I read following here: Unambiguous grammars do not always generate a DCFL. Example: For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-...
user avatar
  • 1,547
2 votes
0 answers
201 views

Simple languages that are not of type-1?

To present interesting type-0 grammars to my students, I am looking for a very simple example of a type-0 language (=recursively enumerable language) that is not of type-1 (=not context sensitive). I ...
user avatar

1
2 3 4 5 6