0
votes
2answers
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: ...
2
votes
3answers
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 ...
0
votes
1answer
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
0
votes
1answer
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
0
votes
1answer
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!
-1
votes
1answer
45 views

CFG and closure properties

I am solving one problem and I urgently need a hint to solve one problem: Use closure under union to show that the following language is context-free $$\left\{a^mb^nc^pd^q : n=q,\ \text{or}\;\ ...
1
vote
0answers
52 views

Non context-free languages closed under reverse

Is this sentence true or false? I'll be glad for some explaination L is not context-free, then its reverse is also not context-free Thanks in advance
3
votes
1answer
117 views

Proving a language is not a CFL although it can be pumped

Let $L=\{a^mb^nc^k\mid k\le \min(m,n)\}$ $L$ can be pumped with the pumping lemma for Context Free Languages which makes it very difficult to prove it is not a Context Free Language. Any idea how to ...
1
vote
1answer
84 views

Finding an appropriate value to contradict the pumping lemma.

I am trying to prove that $L=${$a^mb^n | n=m^2$} is not a CFL with the help of the pumping lemma for CFL's. I chose $w=a^mb^{m^2}$ = $a^{m-S}a^Sb^Tb^{m^2-T}$ $\in L$ And now in order to contradict ...
0
votes
3answers
611 views

Are these languages context free or not?

$L_1=\{a^nb^mc^nd^m \mid m,n >0\}$ $L_2=\{a^nb^mc^md^n \mid m,n >0 \}$ $L_3=\{a^mb^n \mid m+n\text{ is a prime number}\}$ $L_4=\{a^mb^n \mid n=m^2\}$ $L_5=\big\{ww^R\#ww^R \mid w \in \{a,b\}^* ...
0
votes
2answers
526 views

prove (by grammar or closures) that the prefix language is context free

I have a language $L$, which is context-free, and I have $Pref(L)$, which is the language of all the prefixes of the words in $L$. I need to prove that $pref(L)$ is context free only with closures or ...
0
votes
1answer
125 views

Show with closures that L is not context-free

Consider this language: $$ L = \{a^n b^{2n} a^n \mid n \ge 0\}$$ I need to show only with closures that it's not context-free. (Actually, I can show it as I wish, except for the pumping lemma for ...
2
votes
2answers
138 views

Prove or disprove (with closure properties or using grammars)

1) Define $L = \{a^i*b^j*c^k*d^m \mid \text{ if } a=1 \text{ then } j=k=m\}$. Is $ L$ a context free language ? 2) If $L$ is a context free language then $\mathrm{Mirror}(L) = \{ww^r \mid w ...
1
vote
1answer
150 views

Decide if a formal language is a Context-free language

Let $L_1$ be a regular language. Let $L_2$ be a Context-free language. Let $L = \{w \in L_1 \mid w = \alpha_1\phi_1\alpha_2\phi_2\ldots\alpha_n\phi_n : \alpha_1\alpha_2\ldots\alpha_n\in L_2$ ; ...
2
votes
2answers
142 views

Showing a language is context-free with closures

Let $L_1$ a regular language and $L_2$ a context-free one. I need to show that $$L = \{w \mid w = x_1y_1x_2y_2\dots x_ny_n \mbox{ where } x_1x_2\dots x_n \in L_1 \mbox{ and } y_1y_2\dots y_n \in ...
0
votes
2answers
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 ...
0
votes
1answer
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$), ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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, ...
2
votes
1answer
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 ...
0
votes
2answers
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?
3
votes
3answers
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. ...
2
votes
1answer
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*} ...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
1
vote
2answers
204 views

Prove that [ContextFreeLanguage - RegularLanguage] is always a context free language, but the opposite is false

Let L be a context-free grammar and R a regular language. Show that L-R is always context-free, but R-L is not. Hint: try to connect both automata) The above hint did not help me :(
3
votes
2answers
5k views

Question regarding Context Free Grammar exercises

I'm working on the exercises in "An Introduction to Formal Languages and Automata" 4th Ed textbook by Peter Linz. Since there are too few answers given in the back of the book, I wasn't able to check ...