# Tagged Questions

Questions related to formal languages, grammars, and automata theory

44k 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 ...
29k views

### How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
27k 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 ...
70k views

### How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
5k views

### How to prove that a language is context-free?

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ...
2k views

### How to show that L = L(G)?

Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
2k views

### What is the difference between an algorithm, a language and a problem?

It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
4k views

### Show that { xy ∣ |x| = |y|, x ≠ y } is context-free

I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question? Anyway, here'...
708 views

### Determining capabilities of a min-heap (or other exotic) state machines

See the end of this post for some clarification on the definition(s) of min-heap automata. One can imagine using a variety of data structures for storing information for use by state machines. For ...
955 views

### What are the possible sets of word lengths in a regular language?

Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$: $$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$ Which sets of integers can be the length set of a regular language?...
742 views

### Converting to CFG from a CFL? [duplicate]

I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me. Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
304 views

### How do I find a regular expression for a particular language?

I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what ...
818 views

477 views

### Is $A$ regular if $A^{2}$ is regular?

If $A^2$ is regular, does it follow that $A$ is regular? My attempt on a proof: Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$. Since concatenation of two ...
1k views

### Languages that satisfy the pumping lemma but aren't regular?

Given a regular language $L$, then it is easy to prove that there is a constant $N$ such that is $\sigma \in L$, with $\lvert \sigma \rvert \ge N$ there exist strings $\alpha$, $\beta$ and $\gamma$ ...
2k views

### Is the complement of { ww | … } context-free?

Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not? I'...
19k views

538 views

### Which languages do Perl-compatible regular expressions recognize?

As the title says, I spent a couple of hours last weekend trying to wrap up my mind about the class of languages matched by Perl-compatible regular expressions, excluding any matching operator that ...
2k views

718 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 ...
586 views

### Are context-free languages in $a^*b^*$ closed under complement?

The context-free languages are not closed under complement, we know that. As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
202 views

### Is {wxw^r} a regular language?

Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why? The notation $W^{\mathrm{R}}$ means the reverse string of $W$? If we consider the best answer in this solution, ...
377 views

### Is regularity of the language accepted by a given Turing machine a semi-decidable property?

Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
1k views

### If $L$ is a subset of $\{0\}^*$, then how can we show that $L^*$ is regular?

Say, $L \subseteq \{0\}^*$. Then how can we prove that $L^*$ is regular? If $L$ is regular, then of course $L^*$ is also regular. If $L$ is finite, then it is regular and again $L^*$ is regular. Also ...
1k 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. ...
2k 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-...
724 views

### Are DCFLs closed under reversal?

According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
1k views

### Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state

I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question. The question states that the PDA has at most 2 states. Clearly 1 will ...
410 views

I am trying to solve this question which appeared in previous exam paper Can someone help me what i am failing to understand For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy ... 3answers 208 views ### Regularity of “middles” of words from regular language I need some help with the following problem. Let$L \subseteq \Sigma^*$be a regular language. I have to prove that the language$P = \{\alpha \mid \beta\alpha\gamma \in L, \beta,\gamma \in \Sigma^*\}$... 1answer 104 views ### Is the language of all ucv with u ≠ v context-free? Is$L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^* , w_1 \neq w_2 \}$a CFL? In my opinion it is not since if we want to know the inequality of$w_1$and$w_2$we must be aware of their equality and that is ... 2answers 301 views ### Find a pushdown automaton for { x#y ∣ x ≠ y } I was told to built a PDA that recognizes the following language: $$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$ My attempt is basically to push$x$to the stack for every$1$and$0$... 1answer 127 views ### Prove the equality of two concatenations of words [closed] Let$x$,$u$,$v$,$w$,$y$,$x'$,$u'$,$v'$,$w'$,$y'$be words. If$y'x' = xyy'u'x' = xuyy'v'x' = xvyy'w'x' = xwyy'v'u'x' = xuvyy'w'v'x' = xvwy$all hold, then I need to prove ... 2answers 918 views ### Are supersets of non-regular languages also non-regular? I have to proof that if$L_1 \subset L_2$and$L_1$is not regular then$L_2$it not regular. This is my proof. Is it valid? Since$L_1$is not regular, there does not exists a finite automata$M_1$... 2answers 991 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 ... 4answers 6k 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$.... 3answers 10k views ### Infinite Language vs. finite language I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory. I think the root of the trouble is that a language like$L=\{ab\}^*$is infinite in the sense ... 2answers 2k views ### Are regular expressions$LR(k)$? If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ... 3answers 570 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 ... 1answer 476 views ### Algorithm to test whether a language is regular Is there an algorithm/systematic procedure to test whether a language is regular? In other words, given a language specified in algebraic form (think of something like$L=\{a^n b^n : n \in \mathbb{N}\...
Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable? I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, (\$N \...
Is the language $$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$ context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.