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
0answers
19 views

Theory of Computation Resources

I'm currently taking the theory of computation at school. Some stuff covered makes sense, but some topics I feel like I'm missing the big picture. Is there an equivalent of theory of computation and/...
0
votes
0answers
16 views

Why are CFL not closed under set difference, and complementation? [duplicate]

I was wondering why CFL are not closed under set difference, and complementation can anyone explain? I tried searching, but no luck.
3
votes
3answers
412 views

Context-free grammar of the concatenation of a string S and subsequence of reversed S

I have to find a Context-Free grammar that generates the language: $L_1 = \{x\#y\ |\ y$ is a subsequence of $x^R$, and $x\in\{a,b\}^*\}$, $\Sigma=\{a,b,\#\}$ The concatenation of two mutually ...
1
vote
1answer
64 views

Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$

I want to formally write the equivalence classes of the following language: $$L_k = \{w \in \{0,1\}^*\mid\text{ the } k\text{-th bit of }w\text{ from the right is } 1\}$$ I understand the definition ...
2
votes
0answers
32 views

Pumping lemma for L = {a^i b^j c^k: i < j < k}

I had a question regarding a specific proof I found online that I had some concerns with, I have quoted it below. Show that the language L = {a^i b^j c^k: i < j < k} is not a context-free ...
6
votes
0answers
148 views

Is it decidable if this zipping operation gives a context-free language?

Motivation Consider the following languages, are they context-free? $\{x \# y: x \neq y\}$ $\{x y: |x|=|y|, x \neq y\}$ $\{x \# y: |x|=|y|, x \neq y\}$ $\{x y: |x|=|y|,d(x,y)>1\}$ $\{x x\}$ The ...
2
votes
1answer
44 views

Context Free Grammar $L=\{a^ib^{2i}c^{2i} | i>1\}$

In one of my exams I needed to find a CFG for $L=\{a^ib^{2i}c^{2i} | i>1\}$. however, it really seemed to me that it is not a CFG. I tried to show it is not using the pumping lemma, and think I ...
2
votes
1answer
39 views

How can the union of two 'context-free but not regular' languages be regular?

I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language: If $L_1$ and $L_2$ are 'context-free but not regular' languages, defined ...
4
votes
1answer
84 views

A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

It is known that a PDA with two stacks is equivalent to a TM. On the other hand a PDA with one stack is capable to recognise only context-free languages. Hence there is a kind of a gap between the ...
0
votes
1answer
19 views

Given a certain context sensitive grammar, can one find out if a simpler context free grammar exists?

Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, ...
1
vote
1answer
15 views

Context-free grammar for tautologies in one variable

Construct a context-free grammar for the set of tautologies in $p$ - that is, the set of formulae in $\{p, \text{true}, \text{false}, \land, \lor, \lnot, (, )\}$ which evaluate to $\text{true}$ for ...
1
vote
1answer
36 views

Proof that $\{0^i1^{i^2}:i\in\mathbb{N}\}$ is not context free

I am to prove that $L :=\{0^i1^{i^2}:i\in\mathbb{N}\}$ is not context-free. I presume that I can do this with the Pumping Lemma and the word $0^p1^{p^2}$, where we assume for a contradiction that $L$ ...
0
votes
0answers
25 views

Is this language Deterministic?

I came across this question in Peter-Linz today, Is the language L= { a^nb^n : n>=1 } U {b} deterministic ? My doubt is that say we have a case like this {a^5 b^6} U {b}, after popping 5 a's from the ...
0
votes
1answer
41 views

find derivation trees for CFG

I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below. I want to know how many possible derivation trees are there from this grammar. $$\begin{align}V_n&=\{expr,term,...
2
votes
1answer
63 views

Are Context Sensitive Grammar with Polynomial Complexity Time?

Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space. Assuming a Deterministic Parser is the one which can parse unambiguous grammars in ...
1
vote
1answer
58 views

Can CYK Parsing algorithm generate the parsing tree in O(n^3)?

I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free ...
1
vote
1answer
29 views

Is the difference of two context-free languages still context-free?

i am asking myself the following question: Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right? but I do not know how to prove it.
0
votes
1answer
12 views

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?

I understand the difference in the parsing tables of the above 4 parsers. I understand that CLR>LALR>SLR>LR(0) in terms of power. Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),...
0
votes
1answer
21 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}...
2
votes
2answers
71 views

Using pumping lemma to show a language is not context free(Complicated)

How can i show that the following long language is not context free using the pumping lemma? $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}...
0
votes
1answer
35 views

Construct NPDA for the language

$L=\{w \mid w \in \{a,b\}^*$, $\text{the number of a's is at least the number of b's} \}$ I'm stuck trying to build an NPDA that accepts $L$.
0
votes
1answer
60 views

$L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma

How I use the pumping lemma to prove that the language $L = \{ a^{j!} \mid j \geq1\}$ is not context-free?
1
vote
1answer
48 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: ...
3
votes
1answer
35 views

Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?

In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1] In fact, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although ...
2
votes
1answer
37 views

Is $L(G) \subseteq L(R)$ decidable?

Is the following problem decidable? Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$? It is given that the following problem is undecidable Given a ...
1
vote
1answer
37 views

Wikipedia says this grammar is LR(0), but Grammophone says it is not; is it?

E -> E * B . E -> E + B . E -> B . B -> 0 . B -> 1 . I am confused because Wikipedia cites this grammar as an example of an LR(0) grammar ...
2
votes
3answers
79 views

Context free grammar for language with even number of $0$'s and $1$'s

I want to create a Context-Free grammar that generates the language $$ L = \{ w \in \{0, 1\}^* |\ \text{number of $0$'s is even, and number of $1$'s is also even} \}. $$ I came up with $$ S \...
0
votes
2answers
41 views

Help: Context Free Grammar [closed]

Construct the CFG given the following language: $$\{a^i \; b^j \; c^k \;|\; i = j \; or \; j = k \}$$
2
votes
1answer
21 views

Help with figuring out if MAX(L) is a CF language

We call the word $x_1$ a true prefix of the word $x$, if a non-empty word $x_2$ exists so that $x=x_1x_2$. For the language L (over some finite $abc$..). We define MAX(L) as: $MAX(L)$ = {$w_1 \in L $|...
2
votes
2answers
18 views

Confused about 3rd rule of CFG pumping lemma

Let $L = \{\space ww \space | \space w \in \{0,1\}^*$} (need to prove that $L$ is not CFL) Assuming $L$ is CFL we can use the PL and split $s=uvxyz$ and we choose $s = 0^p1^p0^p1^p$ where $p$ is the ...
5
votes
1answer
47 views

Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?

Are there languages $L_1$, $L_2$ such that such that $$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$ and two other languages such that $$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$ And if so, what are they? How ...
1
vote
1answer
36 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
0answers
23 views

CYK algorithm - how to handle unknown terminals given in a sentence to parse?

There is a given treebank which we derive the Probabilistic context free grammar. I wonder how do one handles with a given sentence which includes terminals that don't exist in the derived rules? Is ...
1
vote
1answer
58 views

Connection between non determinism and LL(1) conflicts

I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it. As per my understanding non deterministic context free grammar is a context free grammar ...
2
votes
3answers
131 views

concatenation of context sensitive and context-free is context sensitive or not?

Assume that $L_1$ is context sensitive language and $L_2$ is context free language, is the language $L_1 * L_2$ context-sensitive or not? I almost sure that is not, but can't prove it.
1
vote
1answer
68 views

Context free grammar for a palindrome of even length + cc

Suppose the language is $\{AA^R: A \in \{a,b\}^*\}$. I know that I can make a context free grammar for it: $$S\to aSa \mid bSb\mid\epsilon$$ Now if the language was $\{AA^Rcc: A \in \{a,b\}^*\}$, ...
3
votes
3answers
88 views

CFG for all strings of a’s and b’s that contain a different number of a’s and b’s

I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this: S→A|B A→aE|aA|EA B→bE|bB|EB E→aEbE|bEaE|Λ ...
3
votes
1answer
50 views

Complement of language $\{ x \in \{a,b,c,d\}^* : \exists$ prefix $y$ of $x$ such that $||y|_a - |y|_b|\leq 10 \}$

Is the complement of the following language a regular language? $$L = \{ x \in \{a,b,c,d\}^* : \exists \text{ prefix }y\text{ of }x\text{ such that }||y|_a - |y|_b|\leq 10 \}$$ My first thought is ...
2
votes
2answers
57 views

Writing a grammar for lambda calculus

I'm trying to write a context-free grammar (to be feeded to lark) for parsing lambda calculus expressions. Basic version of it, as presented by most sources, looks like: ...
3
votes
1answer
53 views

Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?

Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language? It certainly isn't regular, but is it context free? I'm having trouble creating ...
3
votes
1answer
66 views

Language whose intersection with a CFL is always a CFL (2)

This is a follow-up to this question, which asks for an example of a non-regular language $L$ which satisfies the following condition, intersection resilience: If $L'$ is context-free then so is $L ...
1
vote
1answer
27 views

Acceptance problem for CFGs is not regular

Let $ACFG$ be the language of all encodings $(C,x)$ where $C$ is a context free grammar that generates a language containing $x$, i.e. $ACFG$ is the acceptance problem for context free grammars. It ...
0
votes
0answers
40 views

What does pump down means in this solution?

Problem text (from Sipser's "Introduction to the Theory of Computation"): 2.42 Let $E = \{1,\#\}$ and $Y = \{ w \mid w = t_1\#t_2\# ...... \#t_k \, \text{for $k \geq 0$, each $t_i \in 1^*$, and $...
1
vote
1answer
41 views

context-free grammar for comma-separated list with comments

I'm trying to write a context-free grammar for a comma-separated list of statements with comments. It is trivial if the comma appears at the end of a statement. It is trivial if the comment is ...
3
votes
0answers
44 views

Conditions that imply closure under intersection of context-free languages

Context-free languages are not closed under intersection. Suppose $L_1, L_2 \in CF \setminus REG$ (i.e., $L_1,L_2$ are context-free but not regular). Are there well-known theorems (and/or whole ...
2
votes
1answer
63 views

In what sense a type of parser is less power than the other?

I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers. I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the ...
5
votes
1answer
240 views

How to prove the emptiness of intersection of two context free languages is undecidable?

Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful. Do you maybe ...
1
vote
1answer
31 views

How to prove that a language is not context-free using pumping lemma

I'm trying to prove that that language isn't a context free: $ L = \{ w11w \mid w\in \Sigma^* = \{0,1\}\}$ I succeed to prove that $L = ww$ isn't context free, but not the language above. What ...
0
votes
0answers
34 views

Find PDA for CFL = {x#y | |x| = |y| and x ≠ y} [duplicate]

I am studying push down automata. When I read a solution for showing $L = \{x\#y \mid x \neq y, x,y \in \{0,1\}^*\}$ is a CFL, I could understand $L = L_1 \cup L_2$, $L_1 = \{x\#y\mid|x| \neq |y|\}$, ...
1
vote
1answer
43 views

Creating a CFG from a specific CFL

I am pretty desperate finding the correct context free grammar for the following language: $$L=\{a^lb^mc^n \mid l,m,n \in \mathbb{N}_0, \, l\geq 2n+m\}$$ I would really appreciate if anyone could ...