Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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
3 views

Proving the decidability of whether a CFG generates a particular string or not

Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$. Consider the language $A_{CFG}$ = { <$G$, $w$> | $G$ is CFG that generates $w$ }, where <$G$, $w$> is a string ...
1
vote
1answer
27 views

Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form

The grammar have the following producitons, \begin{align} S&\rightarrow aTbS \mid\epsilon\\ T&\rightarrow aTb\mid\epsilon \end{align} Already turned this homework in, but I need to convert ...
0
votes
1answer
20 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
0
votes
0answers
34 views

How to find a context-free grammar from a difficult language? [duplicate]

Some Languages are trivial to find their respective context-free grammar. Like for example $ L= \{a^nb^n: n \geqslant 0\}$. However some are really difficult to solve. I would like to have some advice ...
-2
votes
0answers
9 views

How to remove useless productions while converting push down automata into context free grammar [closed]

Here is the half solved example of the problem. (https://i.stack.imgur.com/IkOwz.jpg)
2
votes
1answer
24 views

$L=\{a^ib^i|i\geq0\}$, cfg for $L^2$

$L=\{a^ib^i|i\geq0\}$, cfg for $L^2$ can you write cfg for $L^2$ where $L=\{a^ib^i|i\geq0\}$? the professor's answer sheet says it's $S\to AA\\ A\to aAb|\lambda$ but I think it is wrong because two ...
1
vote
1answer
41 views

Context-free grammar how to have same number of variables within a language

I am trying to get a CFG for the language: The set $A$ of odd-length strings in $\{a,b\}^*$ whose first, middle and last symbols are all the same. (some example of correct answers would be: a, aaa,...
1
vote
1answer
39 views

Context-free grammar how to have unequal number of a's on either side of b

I have been trying to create a CFG for the set $\{w=a^iba^j \mid i \neq j\}$. To my understanding, there are essentially 2 scenarios, one where there are more $a$s on the left side of $b$, and one ...
3
votes
1answer
22 views

How to split a context-free language into three sub-languages?

I try to split the language $$ L = \{a^ib^j \mid i \neq 2j, i \neq 3j\} $$ into three languages \begin{align} L_1 &= \{a^ib^j \mid i < 2j\} \\ L_2 &= \{a^ib^j \mid 2j < i < 3j\} \\ ...
0
votes
0answers
32 views

How to prove that L(G) is not regular by contradicting the pumping lemma?

I am trying to prove that this language is not regular by contradicting the pumping lemma. I have been reading and looking at examples but all the examples I have seen is in the for of a REGEX. I am ...
1
vote
1answer
35 views

I want to design a context free grammar for the following [closed]

This below language $$L = \{ w \in \{a, b\}^n : \lvert w\rvert \text{ mod } 3 = 0 \}$$ where $n \geq0$.
1
vote
1answer
31 views

How to show that A is not regular?

Let Σ = {0, 1, ⊕, =} and define a language A as follows: A = {x = y ⊕ z | x, y, z are binary integers, and x is the XOR of y and z}. For example string “1011 = 1111 ⊕ 0100” is in A, whereas string “...
0
votes
0answers
24 views

Conversion of left-recursive context-free grammars to strongly equivalent ones without left-recursion

It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-...
0
votes
0answers
43 views

Is Python's Grammar in a known Category between CFG and CSG?

I have a high level understanding of formal languages and grammars, and I'm familiar with the four major types of grammars in Chomsky hierarchy. I was interested in knowing the classification of ...
0
votes
1answer
22 views

Examples of Regular, Context-free and Context-sensitive languages

Assume the languages: $$ a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \} $$ $$ b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \} $$ $$ c)\,L_3 = \{ w \in {0,1}^* | \,...
1
vote
1answer
30 views

Is following grammar has language which is inherently ambiguous?

Grammar is as follow: $S \rightarrow aaAb | aab | A$ $A \rightarrow aaAb | aAb | \epsilon$ I think that this grammar has equivalent unambiguous grammar as follow. Let’s first rewrite the grammar ...
1
vote
2answers
38 views

Doubt regarding Chomsky Hierarchy, CFG and CSG

I was following a discussion on a website, where a fellow scholar claims that this grammar S→ aAa | bAb | ϵ A→aA | bA |ϵ is not CSG, so it should also NOT be a CFG. But this grammar properly ...
0
votes
1answer
27 views

Whether the given language is a CFL or not?

Let $L$ be a language defined over $\Sigma = \left \{ a, b \right \}$ such that $L = \left \{ x\#y \mid x,y \in \Sigma^*, \# \text { is a constant and } x \neq y \right \}$ State whether the language ...
2
votes
2answers
41 views

DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$

I need some help with the following task: I have to construct a DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$. How can I recognize that the new ...
0
votes
0answers
18 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
442 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
68 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
53 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
157 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
48 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
44 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
95 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
22 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
27 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
43 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
67 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
156 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
20 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
22 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
78 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
36 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
63 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
58 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
38 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
49 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
40 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
97 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
42 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
20 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
38 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 ...