# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

1,977 questions
46 views

### Reusing variable in converting grammar to Chomsky Normal Form

I'm not sure if reusing variable is allowed in CNF. For example, I have this grammar not in CNF. So I have to convert it to CNF. ...
70 views

### How does this answer for automata and Hamming distance not lead to inconsistencies?

I had already been given the answer by the TA in class, but I don't understand it. I'm not asking for the answer on a homework problem or anything. The problem: The Hamming distance ("distance") of ...
31 views

### Strings which are not in a language generated by a Grammar

I have the following question and its solution Here T -> XTX since T -> X and X->b S ->XbX since X->a S->aba So,why is option 3 not accepted ?
20 views

### Generalization of formal grammars - production rules with more general functions?

Usually formal grammars have production rules in the format N=tNt where simple concatenation function is used for the expansion of the nonterminal. https://www....
84 views

### How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.（\| is the escape character, since | is a special character in grammar's pattern). ...
53 views

### Proving that L is not regular by showing that $\equiv_L$ has infinite index

Proving that L is not regular by showing that $\equiv_L$ has infinite index. $\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0} My ideas: theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
57 views

### context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$

Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$ Generate a cfg of $L_n$ For n = 1, 2, 3 Informally, x is in $L_n$ means some palindrome of at least length n is a ...
34 views

### What is the minimum pumping length of the union of two languages?

If I have two languages L1 and L2 that are pumpable, what is the minimum pumping length for the union of them? Does it differ if either of them contains just one string like 001?
52 views

### How to add decimals to formal grammar?

I have a formal language that describes digit production like <digit> ::= 0|1|2|...|9 and I need to intruduce fraction to write decimals like ...
237 views

### A,B decidable: proof that A\B is decidable too

For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too. My idea is as follows: If B is empty or doesnt have elements in common with A, then A\B is ...
390 views

### Minimizing DFA - Dead state elimination

Following is a Question from a competitive exam, it is given that the solution is A but I don’t know why the dead state 4 is not eliminated.Dead states like 4 which has transitions only to itself, ...
15 views

### Base-k representations of polynomials: state of art [closed]

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

### What is the regular expression for the following language?

What is the regular expression for the following language? $$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$ maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$ Is it true??
52 views

### Regular expression for words where the same symbol can repeat at most two times consecutively?

Having the alphabet $\{a, b\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol? For example, I can't have ${baaab}$ nor ...
653 views

### Does a notion of a context-free complete language exist?

Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?
184 views

### Is the union of 2 non context free languages always non context free?

Let $L_1 = \{a^nb^nc^n\}$ and $L_2 = \{a^ib^jc^k \mid i\ne j\text{ or }j\ne k\}$ (which I think is a non Context free but I am not sure) So, $L_1 \cup L_2$ will give $L_3 = \{a^*b^*c^*\}$ which is a ...
130 views

### Is the power of a regular language regular? Is the root of a regular language regular?

If $A$ is a regular set, then: $L_1=\{x\mid\exists n \geq0, \exists y \in A: y=x^n\}$, $L_2=\{x\mid \exists n \geq0, \exists y\in A: x=y^n\}$. Which one of them is regular? My reasoning is since ...
23 views

### Can a context-senstive gramma contains production rule $cB\rightarrow Bc$?

Some textbook show that the grammar $G=(N,T,P,S)$ below belongs to context-senstive grammars: S->aSBC S->abc cB->Bc bG->bb where N={S,B}, T={a,b,c}. I am confused by the fact that the production ...
168 views

### Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma

I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it. Question Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$...
98 views

### Pumping Lemma Question: About the cases for y in the xy^iz criterion

Problem statement: Let $\Sigma = \{a, b, c\}$, and consider the task of multiplication encoded in the language $L = \{a^n b^k c^{nk} : n \geq 0, k \geq 0\}$. Prove that L is not regular using the ...
74 views

### Is $\{a^mb^nc^{mn}\mid m>n\}$ a context-free language? [duplicate]

Been trying to figure it out for an hour myself and another hour looking around, I cannot find anything with the $c^{mn}$ part. $$L=\{a^mb^nc^{mn}\mid m>n\}$$
47 views

### Context-Free Grammar from this language

I'm having difficulties with an exercise in a theoretical CS class. The problem is: let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast ...
45 views

### unambiguous context-free languages and complementation

I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages: Is the complement of an unambiguous ...
151 views

### If a language has a regular grammar, is it regular?

If L has a regular grammar, is L always a regular language? A regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language. So would ...
75 views

150 views

### Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?

Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why? I think it's undecidable but can't find any undecidable problem to reduce it to.
166 views

### Non-regular language whose prefix language is regular

I understand that prefix of a regular language is regular, but I am unable to get my head around this: Give an example of a non-regular language $A ⊆ \{0, 1\}^*$ for which $\operatorname{Prefix}(A)$...
89 views

### Prove that every CFL has at least one infinite equivalence class

If we define the Myhill-Nerode relation on a CFL how can i prove that there is at least one infinite equivalence class?
143 views

### What is an infinite language?

I just started reading about formal language theory and what i have learnt so far that: Alphabet is a finite set of symbols. String/Word: is always finite. Because a language is set of strings of ...
123 views

### If $L$ is a regular language, then $s(L)$ is also regular

...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression. For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$. My ...
43 views

### Different iterations of regular expressions

A four-part question dealing with formal languages and regular expressions: How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string? How ...
711 views

### is this language regular and why pumping lemma doesn't work?

I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why?
75 views

### Does there exists a finite automata for the given language?

The question is simple and given as, $alphabets=\{a, b\}$, and language $L$ over them as: $L = \{w: w \ € \{a, b\}^*, (n(a) - n(b)) \ mod \ 3=1\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of ...
264 views

### About the relationship between non-termination and inconsistency?

I've been trying to get into Agda and I noticed that it doesn't have recursion, which implies that it isn't Turing-Complete. From what I could understand, if Agda had recursion, it would make itself ...
133 views

419 views

### Are all finitely recursive context free languages parseable with a regexp?

Let's say I have a context free language. It can be recognised by a pushdown automaton. Chances are it can't be parsed with a regular expression, as regular expressions are not as powerful as pushdown ...
233 views

### Is mathematics context-free?

Anyone who deals with mathematics knows intuitively that it is a different kind of thinking than ordinary common-sense thinking that intelligent people use every day to understand and make decisions ...
x,y are regular expressions, prove this: (xy+x)$^*$x = x(yx+x)$^*$* (* in this expression is kleene star) I am looking for a method that is applicable to prove such questions. I know that proof ...