# Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

1,977 questions
568 views

### A context free grammar proof

There is a problem which I cannot solve. If you give a tip I will be very glad. Prove that following language is not context free: $L= \{ a^nb^m | \gcd(n,m) = 1 \}$. It can be proven using the ...
4k views

### Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?

I'm looking for intuition about when a language is regular and when it is not. For example, consider: $$L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$ which is not a regular ...
674 views

### $L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side. I need to Show that $L$ is regular. I'd relly like some help, I tried to think of any way to prove it but I didn't ...
8k views

### Regular expression for all strings with at least two 0s over alphabet {0,1}

My answer : (0+1)* 0 (0+1)* 0 (0+1)* Why is this incorrect? Can somebody explain to me what the correct answer is and why?
2k views

### Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
435 views

1k views

### Please explain this formal definition of computation

I am trying to attack TAOCP once again, given the sheer literal heaviness of the volumes I have trouble committing to it seriously. In TAOCP 1 Knuth writes, page 8, basic concepts:: Let $A$ be a ...
342 views

### The operator $A(L)= \{w \mid ww \in L\}$

Consider the operator $A(L)= \{w \mid ww \in L\}$. Apparently, the class of context free languages is not closed against $A$. Still, after a lot of thinking, I can't find any CFL for which $A(L)$ ...
4k views

270 views

### Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

I would like your help with the following question: Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of ...
926 views

### Chomsky normal form and regular languages

I'd love your help with the following question: Let $G$ be context free grammar in the Chomksy normal form with $k$ variables. Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ? ...
580 views

Here's a conjecture for regular expressions: For regular expression $R$, let the length $|R|$ be the number of symbols in it, ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup 1)^*| ... 1answer 378 views ### Null Characters and Splitting the String in the Pumping Lemma So I'm really struggling with the pumping lemma. I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question. Here is an example, take ... 4answers 2k views ### Words that have the same right- and left-associative product I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting: Give a non deterministic finite automaton accepting ... 4answers 3k views ### Prime number CFG and Pumping Lemma So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class. I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to ... 3answers 435 views ### Proving a specific language is regular In my computability class we were given a practice final to go over and I'm really struggling with one of the questions on it. Prove the following statement: If$L_1$is a regular language, ... 8answers 65k views ### How to prove a language is regular? There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that$L$is regular, how can I prove that ... 2answers 2k views ### How to prove regular languages are closed under left quotient?$L$is a regular language over the alphabet$\Sigma = \{a,b\}$. The left quotient of$L$regarding$w \in \Sigma^*$is the language $$w^{-1} L := \{v \mid wv \in L\}$$ How can I prove that$w^{-1}L$... 1answer 235 views ### What is a formula for the number of strings with no repeats? I want to count the number of strings$s$over a finite alphabet$A$, that contain no repeats, and by that I mean for any substring$t$of$s$,$1< |t| < |s|$, there is no disjoint copy of$t$... 2answers 121 views ### Is the set of LL(*) grammars the same as the set of CFG grammars? Is the set of LL(*) grammars the same as the set of context-free grammars? 2answers 2k views ### Proof that a language involving$gcd$is not context-free How would you prove that the following language is not context-free? $$L= \{a^n b^m |\, gcd(n,m)=1 \}$$ I suspect the solution uses the pumping lemma, but I'm not sure how to apply it. 0answers 112 views ### Multiples of n is a regular language [duplicate] Possible Duplicate: Language of the values of an affine function Let$C_n = \{x\mid x \text{ is a binary number that is a multiple of } n\}$. Show that for each$n$, the language$C_n$is regular.... 2answers 1k views ### Number of words of a given length in a regular language Is there an algebraic characterization of the number of words of a given length in a regular language? Wikipedia states a result somewhat imprecisely: For any regular language$L$there exist ... 3answers 747 views ### Number of words in the regular language$(00)^*$According to Wikipedia, for any regular language$L$there exist constants$\lambda_1,\ldots,\lambda_k$and polynomials$p_1(x),\ldots,p_k(x)$such that for every$n$the number$s_L(n)$of words of ... 8answers 98k views ### How to prove that a language is not regular? We learned about the class of regular languages$\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ... 4answers 7k views ### Using Pumping Lemma to prove language$L = \{(01)^m 2^m \mid m \ge0\}$is not regular I'm trying to use pumping lemma to prove that$L = \{(01)^m 2^m \mid m \ge0\}$is not regular. This is what I have so far: Assume$L$is regular and let$p$be the pumping length, so$w = (01)^p 2^p$.... 2answers 124 views ### Regular Expression for the language that requires one symbol to occur at least once I am trying to figure out the simplest way to do this using a regular expression. Three symbols a, b, c. The sequence length is unlimited, i.e. *. The symbol a must be somewhere in the sequence at ... 1answer 110 views ### Regular sets have linear growth? Is it true that the set$\{ 0^{n^2} \mid n \in\mathbb{N} \}$is not regular because it does not grow linearly? Regular sets are called regular because if you have a regular set then you can always ... 1answer 134 views ### Power of nondeterministic type-1 min-heap automaton with both a heap and a stack 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. ... 2answers 173 views ### Computational power of nondeterministic type-1 min-heap automata with multiple heaps 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 97 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. ... 4answers 1k views ### Are there other ways to describe formal languages other than grammars? I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies. 2answers 957 views ### Are the Before and After sets for context-free grammars always context-free? Let$G$be a context-free grammar. A string of terminals and nonterminals of$G$is said to be a sentential form of$G$if you can obtain it by applying productions of$G$zero or more times to the ... 1answer 3k views ### How does a two-way pushdown automaton work? Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape. I recently had the question of determining the computational power ... 3answers 1k views ### How to convert an NFA with overlapping cycles into a regular expression? If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as ... 6answers 13k views ### Are Turing machines more powerful than pushdown automata? I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave ... 3answers 181 views ### Language of the graph of an affine function Write$\bar n$for the decimal expansion of$n$(with no leading 0). Let : be a symbol distinct from any digit. Let$a$and$b$... 5answers 1k views ### Language of the values of an affine function Write$\bar n$for the decimal expansion of$n$(with no leading 0). Let$a$and$b$be integers, with$a > 0$. Consider the language of the decimal expansions ... 2answers 2k views ### Decidablity of Languages of Grammars and Automata Note this is a question related to study in a CS course at a university, it is NOT homework and can be found here under Fall 2011 exam2. Here are the two questions I'm looking at from a past exam. ... 2answers 4k views ### How can I prove this language is not context-free? I have the following language$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-... 3answers 262 views ### How can solutions of a Diophantine equation be expressed as a language? I was given the question Where does the following language fit in the Chomsky hierarchy? Nonnegative solutions$(x,y)$to the Diophantine equation$3x-y=1$. I understand languages like$L = \...
Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$? ($T$ is the set of ...
I need to show that $\qquad \displaystyle S = \{(10^p)^m \mid p \geq 0, m \geq 0\}$ is not a regular language using pumping lemma. Can I multiply the product of the powers and express it to: \$S = \...