# All Questions

669 questions
Filter by
Sorted by
Tagged with
374 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)$ ...
453 views

### Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
408 views

### Is $A=\{ w \in \{a,b,c\}^* \mid \#_a(w)+ 2\#_b(w) = 3\#_c(w)\}$ a CFG?

I wonder whether the following language is a context free language: $$A = \{w \in \{a,b,c\}^* \mid \#_a(w) + 2\#_b(w) = 3\#c(w)\}$$ where $\#_x(w)$ is the number of occurrences of $x$ in $w$. I can't ...
327 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 ...
1k 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 ? ...
6k 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 ...
1k 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 ...
189 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$ ...
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 ...
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. ...
5k 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-...
12k views

### Are all context-free and regular languages efficiently decidable?

I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a ...
17k 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'...
81k 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....
4k views

### Is an inﬁnite union of context-free languages always context-free?

Let $L_1$, $L_2$, $L_3$, $\dots$ be an inﬁnite sequence of context-free languages, each of which is deﬁned over a common alphabet $Σ$. Let $L$ be the inﬁnite union of $L_1$, $L_2$, $L_3$, $\dots$; i....
617 views

### How to convert a non-embedding context free grammar to regular grammar?

Please note that I am aware the undecidability of the conversion of context-free grammar to regular grammar. But given the non-embedding property of the input context-free grammar, is there any ...
3k views

### Closure of Deterministic context-free languages under prefix

For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be: $\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$ ie. ...
### Is there a context free, non-regular language $L$, for which $L^*$ is regular?
I know that there are non-regular languages, so that $L^*$ is regular, but all examples I can find are context-sensitive but not context free. In case there are none how do you prove it?