Questions tagged [context-free]

Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

Filter by
Sorted by
Tagged with
0
votes
1answer
214 views

NPDA for $\{w : w \in \{a,b\}^*,n_a(w)\geq n_b(w)+1 \}$

I believe that the following NPDA accepts the language $$\{w : w \in \{a,b\}^*,n_a(w)= n_b(w)+1 \}\,,$$ where $n_a(w)$ represents number of symbol $a$'s in string $w$. Is there a two-state NPDA that ...
0
votes
1answer
789 views

It has been asked to prove that a grammar is unambiguous which seem ambiguous to me

S->aAB A->bBb B->A|epsilon It seems that the string abbbb can be derived by using more than one ways. After using the starting production and the ...
-1
votes
1answer
855 views

How to find the Context-free grammars for this language [duplicate]

give a context-free grammar describing the language L={w∈{a,b}∗∣w is of the form xby, where |x|>|y|}. I had one solution like this ...
-1
votes
1answer
1k views

Formal Languages - Expressive power of Formalisms

I need help with the following question: Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state ...
-1
votes
1answer
1k views

Converting a language to a PDA?

I am trying to convert the follow language $$L = \{0^m1^n \ | \ 0 \le m \le n \le 2m\}$$ We have an exam in 2 days and the professor didn't teach us much about PDA's. They will be on the test though ...
-2
votes
1answer
205 views

Prove that X/Y/Z is context-free

Given languages X, Y and Z, each with alphabet, define X/Y/Z as: X/Y/Z = { w ∈ Σ* | ∃u ∈ Y and ∃v ∈ Z; such that wuv ∈ X }. Prove that if X is context-...
-2
votes
2answers
680 views

If I prove that a language is not a CFL, can I assume it is Turing-Decidable?

Lets say I have just used the pumping lemma to prove a certain L language is not CFL. If it is not CFL can I use that as a proof that it is Decidable? Or is this not enouph and I still have to ...
-3
votes
2answers
2k views

Pumping Lemma for Context-Free Languages for reversal language [duplicate]

Show that the language L = {ww^Rw: w in {a,b}*} is not a context-free language.

1 2 3 4
5