Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

249 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
41
votes
0answers
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 ...
22
votes
2answers
501 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
21
votes
4answers
2k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
15
votes
1answer
557 views

Is the language of words that are unbalanced in the first half context-free?

(Practice exam question in computational models) Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s. Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
15
votes
0answers
241 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 ...
13
votes
0answers
626 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 ...
8
votes
1answer
287 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 ...
8
votes
1answer
306 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}$...
6
votes
0answers
103 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 <...
6
votes
0answers
267 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 ...
6
votes
0answers
362 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 ...
6
votes
0answers
129 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 $$\{...
6
votes
0answers
97 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 ...
6
votes
1answer
539 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}...
5
votes
0answers
95 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 ...
5
votes
0answers
91 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 ...
5
votes
0answers
169 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 ...
5
votes
0answers
88 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 ...
5
votes
0answers
222 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 ...
4
votes
0answers
61 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 ...
4
votes
0answers
111 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 ...
4
votes
0answers
103 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. ...
3
votes
0answers
56 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 ...
3
votes
0answers
34 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 ...
3
votes
0answers
145 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 ...
3
votes
0answers
54 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 ...
3
votes
0answers
62 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 ...
3
votes
0answers
25 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 ...
3
votes
0answers
96 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 ...
3
votes
0answers
54 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 \...
3
votes
0answers
27 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, ...
3
votes
0answers
125 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 ...
3
votes
0answers
148 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 ...
3
votes
0answers
80 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\}...
3
votes
0answers
98 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 ...
3
votes
0answers
51 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, ...
3
votes
0answers
104 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 $\...
2
votes
0answers
56 views

Regular expression vs rational expression

Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$. Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows: $|L| ...
2
votes
0answers
22 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 ...
2
votes
0answers
31 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) := ...
2
votes
0answers
82 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 ...
2
votes
0answers
290 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 ...
2
votes
0answers
176 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 ...
2
votes
1answer
181 views

Brzozowki's algorithm doesn't work for this corner case

I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example: In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
2
votes
1answer
1k 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 ...
2
votes
0answers
65 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, ...
2
votes
0answers
88 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$, ...
2
votes
0answers
101 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 ...
2
votes
0answers
628 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\...
2
votes
0answers
646 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-...

1
2 3 4 5