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
2
votes
1answer
1k views

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$ Prove that both regular languages and CFLs aren't closed under $Perm(L)$. I've tried ...
2
votes
0answers
224 views

Context free grammar as minimal solution of a system of equations

It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example: $$\begin{align*} X &=\{{\epsilon}\} \cup Y\\ X ...
2
votes
1answer
871 views

Pumping lemma for linear languages

Let $L$ be a linear language. Then there is a constant $p$ such that for all $w$ in $L$ with $|w| \ge p$, $w$ can be written as $uvxyz$ where (i) $|uvyz| \le p$ (ii) $|vy| > 0$ (iii) $uv^ixy^iz$ is ...
2
votes
0answers
64 views

Correct bracketing check with rotate operation on position i

Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations: Check whether the sequence is correctly bracketed Rotate bracket ...
2
votes
0answers
75 views

Why CFG can specify structure of sentence but Regular grammar cannot? [duplicate]

CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?
2
votes
1answer
90 views

Can there be a context free language that is not recognizable by a PEG?

This is related to this question. Essentially, I want to know whether my reasoning is correct. We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: ...
2
votes
1answer
2k views

Use pumping lemma to show L is not context free

Show that L = $\{0^{2^n}| n\geq 0\}$ is not a context free language. Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| > 0 and $|vxy| \leq p$. So how do I ...
2
votes
1answer
116 views

Are Context-Free Grammars with only one Production Rule always Unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $\require{cancel} \cancel{S \rightarrow aSSb\;|\;\...
1
vote
1answer
1k views

PDA of the language where the number of a's are NOT equal to the number of b's

I have this NPDA for language L = {w: num_a(w) == num_b(w)} all loops in q1 ...
1
vote
1answer
312 views

Reducing context-free languages with polynomial-time reductions

So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$. Can $L \le_p M$ ? Why or why not? How do polynomial time reductions ...
1
vote
3answers
372 views

Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$

For the purpose of proving that they are not regular, what closure properties can I use to transform the languages $L_a = \{ a^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$ and $L_b = \{ab^{i_1}...
1
vote
2answers
3k views

Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$ [closed]

I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$ $$L=\{a^nb^m\mid 2n<m<3n\}$$
1
vote
1answer
133 views

Confusion with first condition of Chomsky Normal Form

I had a very quick question when it comes to CFG (more specifically the attributes of CNF). I've been browsing over some examples and I've come across a few that confuse me. One such example is this: ...
1
vote
1answer
85 views

Unambiguousness and determinism of CFGs for them to be LR

I came across this statement: Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts. I was ...
1
vote
2answers
1k views

Is intersection of regular language and context free language is “always” context free language

I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align*} L_1 &= ...
0
votes
1answer
253 views

Infinite Union of Recursive language

Question Is Infinite Union of Recursive language is Recursive? I know it is already posted here, but the i am not getting answer also i want to know if my approach is correct. My Approach/Doubt $\...
0
votes
2answers
54 views

if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
0
votes
1answer
141 views

Context free grammar for {a^mb^n | m ≠ n} [duplicate]

I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$. This is what ...
0
votes
2answers
3k views

Can context-free grammar generate $a^{2^n}$? [duplicate]

Context-free grammar can generate the string a 2 n for n≥0 . The production rule P is S→SS|a . The derivations is, for example: 1) S⇒a (this is when n = 0) 2) S⇒SS⇒aa (this is when n = 1) 3) ...
0
votes
1answer
209 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
29 views

Getting from one language to the other using closure properties(automata) [duplicate]

I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}...
0
votes
2answers
364 views

CFG for the language L ={a^n w | w \in {b,c}^*, n= count of b.c in w. }

$L =\{a^nw \mid w \in \{b,c\}^*$, $n=$ #$_b$ + #$_c$$\}$ $\bullet $ #$_b$ denotes the number of $b$'s in $w$ $\bullet $ #$_c$ denotes the number of $c$'s in $w$ I have some trouble designing a CFG ...
0
votes
1answer
2k views

PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Can someone help with this $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
0
votes
2answers
900 views

Finding Language of a CFG

Say you are given the following CFG $G$: $$ S \to S_1 \mid S_2 \\ S_1 \to AbAS_1c \mid \epsilon \\ S_2 \to BaBS_2c \mid \epsilon \\ A \to Aa \mid \epsilon \\ B \to Bb \mid \epsilon $$ What is $L(G)$? ...
0
votes
0answers
123 views

Why does $L=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} \notin CFL$ [duplicate]

Im trying to prove that $L=\{w\#s : |w|=|s|, w \neq s\} \notin CFL$ using the pumping lemma. So I said, let say $L \in CFL$ so by the pumping exists $p$ which is the pumping length of language $L$, I ...
0
votes
1answer
2k views

Is my proof for a context free language correct? Same number of a's as b's

I have the following grammar G: $$ \begin{align*} &S \to aB|bA \\ &A \to a|aS|bAA \\ &B \to b|bS|aBB \end{align*} $$ I am going to prove that this language L(G) consists of words with the ...
0
votes
1answer
891 views

Showing Context Free Grammars that are regular if and only if L(G) = Σ∗.

Suppose that G is a context-free grammar. How can I show that “Is L(G) regular?” is undecidable. Also, prove that L is always context-free but is regular if and only if L(G) = Σ∗. This is what I ...
0
votes
1answer
58 views

DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$

$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$ Any idea? I have problem with this kind of task.
0
votes
1answer
2k views

Multiple-Choice Questions about decidability

I'm working on old MC-Questions about decidability und don't have the answers to the following ones: 1.) $L_1$ and $L_2$ are not decidable $\Rightarrow$ No superset of $L_1 \cup L_2$ is decidable 2.)...
0
votes
1answer
144 views

Closure of context-free languages under “removal of a regular language from the right”

I have a homework that I can't solve can somebody help me? If $\Sigma$ is an alphabet, $R$ is regular and $L$ is context-free. Is the language $$P = \{\alpha\in\Sigma^*\mid \alpha\beta\in L\text{ for ...
-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
832 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 ...
-1
votes
1answer
586 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 ...
-2
votes
1answer
2k views

Why is the language of even-length non-palindromes context-free?

We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$ is a context-free language. Can anyone help me produce a PDA or give me any hint how I can quickly understand why ...
-2
votes
1answer
201 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
531 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