# 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
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 ...
2k views

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 \... 1answer 567 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 ... 0answers 246 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 ... 0answers 629 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 ... 1answer 297 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 ... 1answer 309 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}$... 0answers 104 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 <... 0answers 270 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 ... 0answers 363 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 ... 0answers 130 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 $$\{... 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 ... 1answer 544 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}... 0answers 98 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 ... 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 ... 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 ... 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 ... 0answers 223 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 ... 0answers 64 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 ... 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 ... 0answers 104 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. ... 0answers 56 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_{... 0answers 60 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 ... 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 ... 0answers 164 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 ... 0answers 62 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 ... 0answers 63 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 ... 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 ... 0answers 97 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 ... 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 \... 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, ... 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 ... 0answers 150 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 ... 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\}... 0answers 99 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  only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also ... 0answers 52 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, ... 0answers 105 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 \... 0answers 24 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 ... 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) := ... 0answers 83 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 ... 0answers 299 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 ... 0answers 189 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 ... 1answer 201 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 ... 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 ... 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, ... 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$, ... 0answers 113 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 ... 0answers 641 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\...
Ranked alphabet is very often used in Ranked Trees definition, like here for instance. In that example for given set $\Sigma=\{a,b,c\}$ ranks assigned by arity function \$ar : \Sigma\rightarrow\mathcal{...