# Tagged Questions

450 views

### Find CFG for $a^i b^j c^k$ with $!(i=j=k)$

I need to show that the following language is context free: It contains all words $a^i b^j c^k$ with the condition that there're not exactly as many a's and b's and c's. I would write it like this: ...
693 views

### Find push down automata and context free grammar

I have the following language: $$L = \{a^nb^{2n+1} \mid n \ge 0\}$$ I must find the push down automaton and a context free grammar for the language. For the push down I have no idea how to ...
121 views

### Homorphism and Context Free Grammar

Could you explain me concept of homomorphisms and usage of it to the following problem which requires to prove that $L$ is not context-free? $$L=\{ba^{n-1}ba^nb:n\ge 1\}$$ Thanks
46 views

### Pumping lemma and CFG

I am solving problem in pumping lemma for context-free languages. I want to ask a hint for the following problem $$L=\big\{www:w\in\{a,b\}^*\big\}$$ Thanks
74 views

### Pumping lemma for CFG

it is another my question. Can you give me hint to solve the following problem? Prove that $L=\left\{a^{n^2}:n\ge 0\right\}$ is not a context-free language? Thanks!
45 views

358 views

### is this language context-free? a tricky one

Is this language context-free? $$L = \{a^nb^nc^{2n} \mid n \ge 0\}$$ It's tricky in my opinion because I know that $a^nb^nc^n$ is not context-free, but can I determine from this that $L$ is not ...
134 views

### Regular grammar and context grammar problems

If $G$ is not a regular grammar, then $L(G)$ is infinte. If $L^*$ is context free then $L$ is definitely context free. If $G$ is a context free grammar that is language is $L$ (meaning $L(G) = L$), ...
195 views

### Building a regular grammar from NFA

I'm requested to make a regular grammar from a given NFA. In this NFA, there's a "death state", which means, when getting to it, there's no way back to the rest of the states (a self-loop to the same ...
279 views

### Regular, Context-free, Recursive, Recursively Enumerable Language Relationships

I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable. If I am given ...
329 views

### Finding a Context Free Grammar for this language

(Paraphrasal of problem 2.48a in Sipser - Introduction to the Theory of Computation, 3rd ed.) The language $L$ consists of all binary strings with a $1$ somewhere in the middle third of the string, ...
162 views

### Proof that language is not context-free.

Is this the appropriate way to show that this language is not context-free? Given the language $L$ containing the words $1$, $101$, $101001$, $1010010001$, where each word $L_n$ is of the form ...
43 views

### Prove $\{0,1\}^* -\{0^i 1^i\mid i \ge 0\}$ is context free?

Is the only way to prove that this language is context-free to construct a Context-Free Grammar that accepts it? If so any hints on how to get started?
807 views

### Write a Context Free Grammar for L = {x#y | x =/= reverse of y}

$x,y$ are in $\{0,1\}*$ So for example 10101#11111 is in the language, but 000111#111000 is not. This just baffles me. ...
286 views

### Confirm that this language is context free?

$$\{a^i b^j c^k \mid i\ne j\text{ or }j\ne k\}$$ Is this language context free? I believe it is based on the following CFG but I would like some confirmation that I'm right. \begin{align*} ...
121 views

### How to prove that $L=\{w \mid \#a(w)=\#b(w)=\#c(w)\}$ is not context free using closure

How can I prove that the language $L = \{w \mid \#a(w)=\#b(w)=\#c(w)\}$ is not context free using closure? EDIT : I know that the language $L_1 = \{a^i b^i c^i \mid i\geq 0\}$ is not a context ...
255 views

### Proving Grammar Correctness

I'm having difficulties in proving the correctness of grammars. The following problem and my pity attempt to solve it show that I may not understand even the basics of such proofs. Very ...