Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,214
questions
0
votes
1answer
69 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
95 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
51 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
86 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
46 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
241 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
43 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
22 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
51 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
49 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
29 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 ...
3
votes
1answer
134 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
190 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
634 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
420 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
60 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
202 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
72 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
70 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
42 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
63 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
82 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
47 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
127 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
269 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
32 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
44 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
60 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 ...
0
votes
0answers
27 views
About Specification of PDA
I was learned NPDA is specified by a tuple $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F) $,
$Q$ is a finite set of states
$\Sigma$ is a finite set of input symbols (input alphabet)
$\Gamma$ is a finite ...
1
vote
1answer
54 views
Proving that the set of grammars generating L or L complement is undecidable
Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
1
vote
1answer
38 views
Undecidability of checking whether all words can be generated from a context-free grammar?
I know it's undecidable, but how to prove it?
Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate ...
3
votes
1answer
60 views
Is there an algorithm to overapproximate a context free grammar by a regular expression?
I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be ...
0
votes
2answers
552 views
Convert this language to Context Free Grammar
I'm having trouble understanding how to convert this language to context free grammar.
$\{a^ib^jc^k\mid i > k, 0\le j \lt3, k \ge 0\}$
Part im getting stuck on is how to deal with a and c, ...
-1
votes
2answers
948 views
CFG for L {a^nb^m | n <= m+3}
I need a Context Free Grammar for this language. I could come up with this solution:
S -> AB
A -> aA | ε
B -> bbbB | ε
But, this grammar is clearly ...
0
votes
2answers
228 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 ...
-1
votes
1answer
176 views
Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 }
$L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \}$
I have trouble about this PDA. Anybody can help me about draw this PDA?
0
votes
0answers
36 views
Is there any grammar parseable by LALR(1) but not LR(1)?
https://en.wikipedia.org/wiki/LALR_parser - as far as I understand, LALR(1) is a simplified version of LR(1), aiming to achieve a greater parsing performance at the expense of reduced power. So, IIUC, ...
0
votes
1answer
59 views
What are the sufficient conditions for a grammar to be unambiguous?
There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous?
For ...
2
votes
2answers
65 views
Operator name in LL(1) computation
I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(...
0
votes
0answers
275 views
a^nb^nc^nd^n using 2-stack PDA
I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n | $ $n \geq 0\}$.
Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and ...
2
votes
2answers
61 views
Why can we (apparently) implement CFG parsers only using (N)DFAs?
I am working on a project in which I need to parse files written in different DSLs. One important feature of these languages is that most of them allow blocks to be nested.
For parsing those files I ...
1
vote
1answer
244 views
Binary strings such that the sum of 0's is not equal to twice the sum of 1's
Construct a context-free language for $L=\{w\in \{0,1\}^* \mid n_0(w)\not= 2n_1(w)\}$. Here $n_b(w)$ is the number of $b$'s in $w$.
I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no ...
2
votes
1answer
133 views
Finding an unambiguous grammar of a language provided by a CFG
I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman.
In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ...
1
vote
2answers
137 views
How do I model line comments in a CFG?
Assume we want to define a context free grammar of say a programming language, where on each line everything after the character # until the end of line is considered a comment and should be ignored. ...
1
vote
0answers
89 views
Accounting for spaces in grammars
Sometimes in a context free language we'd like to require spaces between productions, and sometimes not. For example take the following part from a grammar describing grammars:
...
1
vote
1answer
56 views
Can the complement of a context-free language be regular?
I know that the context-free language is not closed under the complement ,
and the result could be context-free language or non-context free language
but my question is :
is it possible of the ...
2
votes
1answer
34 views
Equivalent unambiguous grammar
Given the grammar:
$S \to AS\mid \varepsilon$
$A \to A1\mid 0A1 \mid \varepsilon$
Generate a new unambiguous grammar that generates the same language as the grammar above.
I have no idea how to ...
1
vote
2answers
49 views
Proving that a specific grammar is ambiguous
How can I prove that the following grammar is ambiguous:
$$ A \to AA\mid B \\ B \to aBb\mid ab $$
I tried finding a string that can be derived in two different ways, but to no avail.
0
votes
1answer
56 views
Crafting a Context Free Grammar
I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem ...
