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

Proving language is not context-free with pumping lemma

I'm trying to prove that this language is not context free using pumping lemma. I am having difficulty as to where to even start on this. $$\{c^{2i} d^j b^{2j} d^k c^{3j} \mid i,j,k \ge 0\}$$
-1
votes
0answers
24 views

A function that maps a context-free grammar G to the context-free grammar G′ [closed]

So i'm really lost on this exercise: Let f be the function that maps a context-free grammar G = (V,Σ,S,P) to the context-free grammar G′ = (V,Σ ∪{a},S,P′), where P′ = P ∪{S →SS}∪{X →a |X → ∈P}. Give f(...
-3
votes
0answers
10 views

Finding out the language generated by a context-free grammar

how can i find out the language that accepted by this cfg : S -> A B | B C A -> B A | x B -> C C | y C -> A D | x D -> y
0
votes
1answer
34 views

References to deterministic time complexity of language classes

It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$. I have found a variety of claims for these classes on the internet. ...
0
votes
2answers
52 views

Equivalence relation between two CFG's

In our course: Automata and Computation there is a definition about Context-Free Grammars which states: "Two CFG's $CFG_{1}$ and $CFG_{2}$ are equivalent if $L_{CFG_{1}} = L_{CFG_{2}}$ where $L_{...
-4
votes
1answer
25 views

Decoding CFG for odd length string-:

S → aX | bX X→ aS | bS | ε This is required cfg, I want to learn how we arrived at this cfg? What steps did we follow to arrive here? Do we memorize some standard ...
-1
votes
0answers
25 views

Say what language is generated by the context-free grammar

In each case below, say what language (a subset of {a, b}∗) is generated by the context-free grammar with the indicated productions. S→ aSa | bSb | aAb | bAa A → aAa | bAb | a | b | Λ I tried to solve ...
0
votes
1answer
44 views

What happens to a Turing Machine if it enters final state but the input is not yet read completely?

In the image, the language of the TM is defined on (a, b, c, d) and there is no transition on final state, but strings consisting of d are also part of the language. In all TM problems I have seen ...
-1
votes
0answers
25 views

PDA for wcw^r confusion

Note-: The transition rules are in the form of inputsymbol, topofstack/operationontopofstack I think this(not the convention but the given PDA) is wrong because we are not doing this case. In state q1,...
0
votes
1answer
23 views

Empty string in an ambiguous grammar?

I'm a bit confused by the role of the empty string in this ambiguous grammar: A' -> A A -> if A B A -> null B -> [empty string] B -> else S So what ...
-1
votes
0answers
32 views

$Prove\; that\; L=a^i b^j c^k: i\le j\le k$ i s not context free language

Proof-: Assume L is CFL. Let p is pumping constant for L. w exists in L such that |w|$\ge p$ Let w=$a^p b^p c^p$ |w|$\ge$3p so everything is fine. Now let us see all decompositions of w such that-: vy$...
-1
votes
1answer
31 views

I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$

If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7. Case 1-: Say vxy contains ab So when I pump v and y, what will get pumped? And how the result would be. ...
1
vote
1answer
29 views

CFG for L={a^i b^j c^i; i,j > 0}

I worked a bit on this and got this-: S->ABC A->aA/a B->bB/b C->cC/c The obvious problem here is I am unable to count number of a's and c's which ...
-3
votes
0answers
33 views

I need a pumping lemma for context free lenguages for this example? [duplicate]

Prove is that a context free lenguage or not $L= $ { $0^k 1^l 0^k; k\geq l; (k,l) ∈ N ∪ 0$ }
0
votes
2answers
116 views

Can I solve pumping lemma for context free language proofs using examples?

Say I need to prove that $L=${$a^n b^n c^n; n\geq 1$} is not context free language I take n=3. w=aaabbbccc Here |w|=9. we know by pumping lemma-: |vxy| $\leq$n so vxy=abb |vy| $\geq$1 so vy=ab Hence I ...
0
votes
0answers
13 views

Tips on making a grammar LL(1)?

So I currently am given the following grammar, and I have to make it LL(1). To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary. But looking at this, it's ...
0
votes
1answer
19 views

What is the subset of CFGs called where each expansion must be the same?

I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and <...
1
vote
1answer
40 views

Is language $a^mb^nc^n, m \not= n$ context free

I need to say Is language $a^mb^nc^n, m \not= n$ context free I managed to find a grammar for $L1 = $ { $a^lb^mc^n | l=m$ or $m = n$ }, but I couldn't find the one I needed. Maybe it is impossible, ...
1
vote
2answers
42 views

PDA with multiple element access - $i$ - access PDA

We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$. Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d &...
0
votes
1answer
23 views

Variant of Chomsky Normal Form for Languages with Strings of Length $\ge 2$

Given a context-free grammar $G$ for a language $L$, where $L$ contains strings of length greater than 2, show that there exists some context-free grammar $G'$ which generates $L$ such that every rule ...
2
votes
1answer
43 views

Proving that the given Context free grammar generates strings with unequal number of a's and b's

Here is the grammar given on the wikipedia: $$ S \rightarrow T \;|\; U \\ T \rightarrow VaT \;|\; VaV \;|\; TaV \\ U \rightarrow VbU \;|\; VbV \;|\; UbV \\ V \rightarrow aVbV \;|\; bVaV \;...
0
votes
1answer
67 views

Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

Context-sensitive languages have context-sensitive grammars, and context-free languages have context-free grammars. Using context-free grammars, we can decide the finiteness and emptiness of context-...
0
votes
1answer
40 views

Difference between Counter-machine and stack machine

I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). My question is counter machine means counter coexist ...
0
votes
0answers
50 views

Whether $L(G)=L(R)$ is decidable for DCFL and CFL?

Let $G_1$ be the context free grammar and $R$ be regular language. Now I have to check whether $L(G_1)=L(R)$ is decidable or not? My approach $\overline{L(G_1)}=\overline{L(R)}$. Now $L(G_1)$ not ...
0
votes
1answer
99 views

Rice theorem could apply except RE language?

You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages. $Q_1:$ So ...
0
votes
2answers
135 views

Regularity of CFG and DCFL

I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...
0
votes
1answer
40 views

Why finiteness problem of CFL is decidable?

We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?
1
vote
1answer
62 views

Why equality is decidable for regular language but not for $CFL?$

There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$ But also there are infinitely many different $DFA$ exists for same regular language. ...
0
votes
1answer
46 views

Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]

We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
1
vote
1answer
57 views

Stuck with shift-reduce conflicts on yacc on grammar to generate palindromic strings on {0,1}

I have written a yacc program for generating palindromic strings consisting of 0s and 1s. Here is the rules section of the yacc program below: ...
0
votes
0answers
26 views

Can we combine two non-terminals and use this as one non-terminal in CFG?

Let's consider this CFG- S->AB [Here, **S** is the starting variable] A->C CB->Cb C->a Now, the question is- Check if ab is a valid string for the ...
0
votes
0answers
25 views

DFA and RE find out the language. Please can you explain?

Find the regular expression describing following languages over alphabet {0, 1}*. ...
0
votes
1answer
45 views

Formal proof of existence of equivalent parse tree for each derivation

Where I can find formal proof of there exists an equivalent parse tree for each derivation? There is a lot of informal proof of equivalency on the internet but I need formal proof to reference it in a ...
4
votes
1answer
119 views

How to prove that the problem $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
0
votes
1answer
48 views

How to use pumping lemma on languages that do not follow a strict structure?

Let me preface this by saying, I do NOT want an example of a proof, I would merely like pointers as to how I could approach this problem. For example, I have a language: $$L = \{w \mid w \in \{0, 1\}^*...
0
votes
1answer
145 views

Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?

I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition: A grammar G is ambiguous if some sentence in L(G) has more than one ...
1
vote
1answer
30 views

Test whether words of less a's than b's or c's but not at the same time is context-free

I want to test whether $L= \{w\in\{a,b,c\}^* \mid |w|_a<|w|_b \text{ or } |w|_a<|w|_c,\text{ but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so. The closest ...
1
vote
0answers
29 views

Algorithm for transforming all left-recursive rules in a grammar into direct left-recursive

I'm probably missing a lot of terminology here, so I'll try to rather be too clear than too vague. I have a Context-Free grammar as an input, that might contain direct or indirect left-recursion ...
2
votes
2answers
120 views

Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $

I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
3
votes
1answer
90 views

Context free grammar for strings with more $a$'s than $b$'s

I would like to prove that the grammar $G$ with the rules $$ S \to SS \mid aSb \mid bSa \mid a \mid \varepsilon $$ generates the language $L = \{w \mid \text{$w$ has at least as many $a$'s as $b$'s}\}$...
0
votes
1answer
72 views

Details wanted on the reduction from Circuit Value to CFG Membership

Consider a Boolean Circuit $C$ which takes $n$ inputs and has one output. Notation: Let $\textit{size}(C)$ be the size of circuit $C$: the total number of gates in $C$. Let $G = (V,\Sigma,R,S)$ be a ...
1
vote
3answers
69 views

A non-CFL over {a,b,c} with a non-CFL complement?

I understand uncountably many such languages exist, and the rational for it is clear to me. I just can't think of one trivial, easy to prove example. For instance, the complement of a^nb^nc^n is CF, ...
-3
votes
1answer
51 views

Designing a context free grammar for a language

Design a grammar for the language $$F = \{x^a y^b zx^b y^a\mid a, b\geq 1\}$$ I'm trying to get a stronger grasp of designing grammars for languages. A thorough explanation of how to design the ...
1
vote
1answer
52 views

Give a context-free grammar

We know that $L$ = { $w$ $\in$ {a, b}* $|$ $|w|_{a}$ > $|w|_{b}$ } This is my answer: $G$ = ({$S$,$A$,$B$},{$a$,$b$},$R$,$S$) $R$ = S $\to$ $AB$ $A$ $\to$ $aA | Aa |B$ $A$ $\to$ $a | abB | Bab | ...
0
votes
0answers
63 views

Proving that $\{ a^i b^j c^{\max(i,j)} \}$ is not context-free

Prove that $L$ is not a Context-free language, where $$L = \{ a^{i} b^{j}c^{h}\mid i,j,h\in \mathbb{N} \wedge h = \max(i,j)\}.$$ I have an idea: It can be divided into two situations: When $i < j$...
1
vote
0answers
39 views

In what sense is a CFDG grammar a context free grammar?

CFDG is described as a language for context free grammars which can generate images. It allows rules to have parameters, but places restrictions on them to ensure the grammar is context free rather ...
0
votes
1answer
49 views

Is $B=\{a^n b^m \mid n \not= 2m\}$ a context free grammar [duplicate]

I was trying to find a grammar that generates $B=\{a^n b^m \mid n \not= 2m\}$ but I couldn't so I'm not sure that it is a CFG. This is what I did : $$ S\rightarrow X \mid aX \mid a \mid b \mid \...
1
vote
1answer
47 views

Proof of an interesting language being non-context free

Let $\Sigma = \{a, b, c\}$ and $L = \{wa^{1 + k + 2n}b^nw^{rev}\mid n, k \in \mathbb{N}_0, w \in \Sigma^*\}$. It is clear that $L$ is context free, but the question is the following: Let $L'$ be the ...
0
votes
1answer
83 views

What's the Context-Free grammar of this language : $L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$ [duplicate]

I was trying to find the context-free grammar of `$L= \{a^n b^m c^p d^q |m+n=p+q, n,m,p,q \geq0 \}$ but I'm stuck. This is what I did so far: $$ S \to X S Y | \lambda$$ $$X \to a|b$$ $$Y \to c|d $$ ...
1
vote
2answers
60 views

If $p(n) := \sum_{i=0}^ka_in^i$ where $a_i\in\mathbb{N}, a_k \ne 0$ AND $k \ge 2$, is $L = \{0^n1^{p(n)} \mid n\in\mathbb{N}\}$ context-free?

I have the really strong feeling it is indeed NOT context-free, since the language $1^{n^k}$ for $k\ge 2$ is not context free (proven by the pumping lemma) and, in a sense, "the order of ...

1
2 3 4 5
30