Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,681
questions
2
votes
1
answer
912
views
PDA for $\{a^nb^m \mid 0 < n \le m \le 3n\}$
I have to design a PDA that recognizes the language $\{a^nb^m \mid 0<n\leq m\leq3n\}$
I tried to partition the stack into 3 partitions with the first partition being the size of $n$ with character ...
- 135
0
votes
1
answer
449
views
Reduce-reduce conflict in SLR vs LALR
I was wondering if I could say any of the following is true.
Given a grammar $G$,
If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$.
...
0
votes
1
answer
672
views
Context free grammar for $1^n 0^m 1^k 0^p$ where $n+k=m+p$
i need to convert this CFL to CFG
$$ L = \{\; 1^n 0^m 1^k 0^p \mid n\ge 2, k,m,p\ge 1, n+k=m+p\;\} $$
I am trying to solve this problem for a few days but i couldn't. Is there anyone to help me? I'm ...
- 11
2
votes
1
answer
96
views
Is the union of two CFLs minus their intersection a CFL?
I've seen the classical proofs of CFLs are not closed under intersection or complement, but I haven't been able to wrap my head around this. Intuitively, I think that this would be not a CFL but I can'...
- 21
0
votes
1
answer
99
views
Any context-free grammar generating a regular language is unambiguous
I am not sure whether this statement is true or not. Could there be an example of CFG generating a regular language and is ambiguous?
- 3
0
votes
0
answers
70
views
Complement of a context free language
Consider the context-free language of balanced parentheses of three kinds:
$$L = \{w \in \{ (, ), [,], \{, \} \}^∗ \mid \text{all parentheses in }w \text{ are properly balanced}\} $$
What will be the ...
- 3
-1
votes
1
answer
97
views
Is a one step derivation grammar context free?
Suppose we have a grammar having a one step derivation like
S -> a
where 'S' is a variable and 'a' is a terminal.
Since this grammar does not pump terminals, can we say that the language generated ...
- 109
0
votes
0
answers
40
views
Find CFG for bin(n)bin(2n+3)^R
Where bin(n) is the shortest binary representation of n.
First, we can see that we can rewrite it as $bin(n)bin(2(n+1)+1)^R$ which implies that the second word will always start from 1.
We can also ...
- 1
1
vote
1
answer
182
views
Decidability for intersection of context free and regular languages
I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the ...
- 13
2
votes
4
answers
296
views
Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}
The language given is $L = \{a^i b^j c^k\mid i+j \ge 2k\}$ for which I need to construct a simplest possible Context Free Grammar.
I tried understanding but I could only go as far as making sense of $...
- 21
0
votes
1
answer
148
views
How to design PDA for this language?
I'm having a hard time trying to build the PDA for this language:
$$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$
I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$...
user145974
0
votes
1
answer
36
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
2
answers
81
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_{...
- 29
-3
votes
1
answer
202
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 ...
- 37
0
votes
1
answer
603
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 ...
- 35
1
vote
2
answers
149
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 ...
- 111
-1
votes
1
answer
48
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. ...
- 37
1
vote
1
answer
294
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 ...
- 47
0
votes
2
answers
287
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 ...
- 47
0
votes
1
answer
29
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 <...
- 103
2
votes
1
answer
871
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, ...
- 21
1
vote
2
answers
83
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 &...
- 15
0
votes
1
answer
52
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 ...
- 15
2
votes
1
answer
135
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 \;...
- 123
0
votes
1
answer
223
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-...
- 346
0
votes
1
answer
88
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 ...
- 346
0
votes
1
answer
210
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 ...
- 346
0
votes
2
answers
560
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 ...
- 346
0
votes
1
answer
210
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?
- 346
1
vote
1
answer
261
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. ...
- 346
0
votes
1
answer
94
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\\\\...
- 346
1
vote
1
answer
232
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
0
answers
86
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
1
answer
70
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 ...
- 101
7
votes
1
answer
842
views
Prove that "If $L$ is a context-free language, is $\overline{L}$ also context-free?" is undecidable
Lately I need to find the decidability of the following decision problem:
If $L$ is a context-free language, is $\overline{L}$ also context-free?
I know that context-free language is not closed ...
- 1,112
0
votes
1
answer
64
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
1
answer
1k
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
1
answer
46
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 ...
- 239
1
vote
0
answers
46
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 ...
- 208
2
votes
2
answers
275
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 ...
- 346
3
votes
1
answer
946
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}\}$...
- 323
1
vote
1
answer
181
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 ...
- 923
1
vote
3
answers
124
views
A non-CFL over {a,b,c} with a non-CFL complement?
I understand uncountably many such languages exist, and the rationale for it is clear to me.
I just cannot think of one trivial, easy-to-prove example.
For instance, the complement of a^nb^nc^n is CF, ...
- 13
-3
votes
1
answer
85
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
1
answer
60
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 | ...
- 13
0
votes
0
answers
124
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$...
- 13
1
vote
0
answers
59
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 ...
- 268
1
vote
1
answer
1k
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 \...
- 111
1
vote
1
answer
83
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 ...
- 175
0
votes
1
answer
409
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
$$
...
- 111