Questions tagged [context-free]
Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
1,687
questions
1
vote
1
answer
91
views
Are there context-free languages whose both intersection and complement of intersection are non-context-free?
It is well known that context-free languages are not closed under intersection or complement. But what about context-free languages $L_1$ and $L_2$, such that $L_1 \cap L_2$ as well as $\left( L_1 \...
- 11
0
votes
1
answer
36
views
Context free grammar $\{0^n 1^m : n,m \geq 0\}$
I just started studying the concept of context-free grammars and I find something very confusing. Watching a video I found someone tackling the problem ${0^n 1^m : n,m\geq 0}$.
I thought that the ...
- 11
0
votes
0
answers
20
views
CFG PL for L=\{a^ib^j \mid j = i^2\}
where i got it from. This was weird so I wanted to try it myself because they way he did it seemed wrong. So this is my attempt is it correct?
I did not add the basic parts of the pumping lemma proof ...
0
votes
1
answer
23
views
What is the name of the diagram used in JSON spec for representing a context-free language?
If you go to the JSON spec page : https://www.json.org/json-en.html, then you'll see the language represented by some diagrams showing graphically what the language looks like. I wondered, does this ...
- 103
0
votes
0
answers
30
views
Two Counter word count language Nondeterministic Pushdown Automata (NPDA) problem actually Context Sensitive unless counters are multiples
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
0
answers
3
views
Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
0
answers
4
views
Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
-2
votes
0
answers
37
views
L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of y
How can I convert this context free langauge to conext free grammar? Please help I can not solve this problem for days.
L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of ...
-4
votes
0
answers
39
views
How do I convert this context free language to context free grammar L1 = {0^i 1^j : i ̸= j, j ̸= 2i} [duplicate]
How do I convert this cfl to cfg L1 = {0^i 1^j : i ̸= j, j ̸= 2i}
1
vote
2
answers
369
views
Does there exist an context free language L such that L∩L^R is not context free?
By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an ...
- 11
-1
votes
0
answers
58
views
Can we give an example Context-Free Language that a DPDA can not recognize [duplicate]
Can we give an example Context-Free Language that a DPDA can not recognize. If we DPDA can not recognize can you explain why?
- 1
2
votes
2
answers
52
views
Derivation trees to show a given grammar is ambiguous
Given the grammar with productions:
\begin{align}
S \rightarrow aSb \mid SS \mid \lambda\\
\end{align}
I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
- 21
0
votes
1
answer
30
views
Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL
I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far.
Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
- 315
0
votes
1
answer
60
views
Is L={0^n 1^n ∣n≥0} context free language?
I looked through many sources which give this as an example for cfl. It also makes sense according to this:
But it fails the pumping lemma test.
Let's take n=5.
According to the Pumping Lemma, we can ...
-4
votes
1
answer
26
views
Which one is an LL(2) but not an LL(1)
I'm pretty sure b and d are ll2 and not one but not 100% sure.
(a) S → aaScc | aaBbc | aaBbb | aBb | ac | Ʌ
B → aBb | Ʌ
(b) S → aaScc | aaBbc | aBb | ac | Ʌ
B → aBb | Ʌ
(c) S → aaScc | aaBbc | B | ac |...
- 1
0
votes
0
answers
71
views
Turing machine for a^n b^m c^n d^m
The state diagram for the initial part of this turing machine given as:
Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
- 101
0
votes
0
answers
31
views
Language of words concatenated with themselves
Let $L$ be a regular language.
Is the language $L_2 = \{ ww | w \in L \}$ context-free? Does it have a name?
- 2,184
0
votes
1
answer
33
views
An elementary question about grammar
Recently, I am studying grammar in automata. And, I have few information about this subject.
I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$.
Is it true if I say that $S\to aASA$ ...
- 13
-1
votes
1
answer
36
views
Write a CFG for a language of the form L_1 ={a^ib^jc^kd^m|i,j,k>=0, i +j +k> m}
I'm currently having trouble coming with context free grammar to describe this language.
My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character ...
0
votes
1
answer
64
views
Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s
Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
- 23
1
vote
0
answers
31
views
How need help to specify a grammar for arithmetic expressions
I am trying to come up with a grammar for arithmetic expressions with the following order of operations:
Parentheses
Factorials
Exponents
Functions / unary plus and minus
Juxtaposition (implied ...
- 111
0
votes
0
answers
41
views
Is $\{ 0^{a}10^{a}1 0^{a}|a \in \mathbb{N}\}$ a context free language?
I was thinking about whether $\{ 0^{a}10^{a}10^{a}|a\in\mathbb{N} \}$ is a context-free language, and I found this post. I am not sure if my understanding is correct or not, but I guess $R = \{ (a,1,a,...
- 101
1
vote
1
answer
191
views
How to prove L := { a^n b^n c^m | n,m >= 0 & n != m } is not context-free?
I have following language $L:= \{a^n b^n c^m \mid n \neq m; n,m \ge 0 \}$ and would like to use proof by contradiction by applying Pumping Lemma for CFLs to show that $L$ is not a CFL.
In any case, i ...
- 13
0
votes
0
answers
28
views
Confused about decomposition in Context Free Pumping lemma
I am trying to decide whether the following language is context free:
$$L = \{ a^nb^{3n}c^n \, | \, n \geq 0 \} $$
Assume $L$ is context-free.
Let $p$ be the pumping length given by the Pumping Lemma.
...
- 1
1
vote
1
answer
73
views
Is $L=\{1^n2^n3^m : n\neq m\}$ context free?
Is the language $L=\{1^n2^n3^m : n\neq m\}$ context free?
I checked and it satisfies the pumping lemma (Right?). Does it also satisfy Ogden's lemma, or any other test for being non-context free?
- 76
0
votes
0
answers
18
views
prove that the language L = { ww | w ∈ {a,b}* } is not context free [duplicate]
I came across this question presented in a past exam. I can see why the language is not context free (you can't know what the first w is, hence you are not able to duplicate it, I hope it makes sense),...
- 11
1
vote
1
answer
53
views
Does this really define a 0L-system?
Looking through old exams I found a problem stated as the following:
Define a 0L-system as a 3-tuple $S = (\Sigma, w, h)$ where $\Sigma$ is an alphabet, $h:\Sigma^* \to \Sigma^*$ is a homomorphism ...
- 13
0
votes
0
answers
34
views
Nonterminal Complexity of a context-free grammar
Suppose $G$ is a CFG.
$G = (N, T, P, S)$,
$Var(G)$ as the cardinality of $N$
$Var(L) $= min {$Var(G)$ | G is a context-free grammar and $L(G) = L$}.
I have a problem in understanding a part of proof ...
- 1
0
votes
1
answer
44
views
Doubt in pumping lema for context-free language
I have a doubt related to pumping lemma in CFL for which I dont find an answer, so I think is very easy because no one wonder about. The lemma says:
My doubt is: Is there any restriction related to ...
-1
votes
1
answer
194
views
Show that the language $L=\{w|w$ has odd length and the middle symbol is a $0\}$ is Context-Free and construct a PDA that accepts it
Were w is any string composed over the alphabet $\Sigma = \{0,1\}$.
For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ...
- 3
0
votes
0
answers
19
views
Decide if complement of context-free language is also a context-free language
Consider the following grammar $G$:
$$S \rightarrow SA \ | \ AS \ | \ aXb \ | \ bXa, \ \ \ X \rightarrow \# \ | \ BXB, \ \ \ A \rightarrow a \ | \ b \ | \ \#, \ \ \ B \rightarrow a \ | \ b$$
Decide if ...
- 13
1
vote
1
answer
78
views
Minimum pumping length of a context-free language
I was studying about the minimum pumping length of the language $L$ containing all palindromes over $\{a,b\}$ from this material about the pumping Lemma for CFLs.
The productions are as follows:
$$S\...
- 113
1
vote
1
answer
39
views
Reformulating the Given Conditions in Decidability Problems
I came across the following question:
Given two context-free languages $L_1$ and $L_2$ is it decidable whether $L_1 - L_2 = \emptyset$ ?
The problem $ALL_{\text{CFG}}$ that states:
Given a CFG $G$ ...
- 165
1
vote
1
answer
51
views
What happens if we remove the length condition on the pumpable part in the pumping lemma for context free languages?
Let $G$ be any CFG Grammar. There exists number $K$ dependent to $G$ so that for each $w\in L(G)$ with length bigger or equal than $K$, we can be write $w=uvxyz$ such that $uv^nxy^nz \in L(G)\; \...
- 13
0
votes
0
answers
25
views
Can a CFG parse tree have a root other than S?
Can a CFG parse tree have a root other than starting non-terminal S? Except for the cases when tree has a height equal to zero and contains only one symbol from the main alphabet.
- 13
0
votes
1
answer
39
views
How can I transfer the following language into an context-free grammar?
My problem of understanding is how to create a new a before the b's if you create new c's.
Hopefully someone can help me out.
0
votes
1
answer
37
views
Find Grammar for L(G) ={a^i b^j c^k | k = i*j ;i, j ≥ 1}
Find a Grammar G, so that L(G) = {a^i b^j c^k | k = i*j ;i, j ≥ 1}
Hello, I have difficulties solving this. I had a similar exercise, where the k was i+j, which was easier, because the solution was to ...
0
votes
0
answers
11
views
Deterministic pushdown automata that checks for a specific variable in nesting levels
I want to define a DPDA based on a set of rules:
one or more uppercase letters ('A'-'Z') is a formula.
one or more lowercase letters ('a'-'z') is a formula.
if X and Y are formulas, then this is a ...
- 1
0
votes
0
answers
52
views
Removing null production from cfg
While removing null production from cfg as below,
S->ABC
A->aA|^
B->bB|^
C->aaC|^
now as shown above we know that A,B and C all are ...
0
votes
0
answers
52
views
How to Remove Left Recursion from this Grammar?
How to remove left recursion in the following Grammar:
S→Bb/a
B→Bc/Sd/e
Im new to this, below is the way I'm doing it:
...
- 1
0
votes
0
answers
45
views
Equivalent context free grammar for every pushdown automaton?
Equivalent context free grammar for pushdown automata
[edit] This machine does not accept L = {a^(n)b^(n)c^(n) | n > 0} and instead accepts L = {a^(2n+1)b^(2n+1)c^(2n+1)}; also, as a side note ...
0
votes
0
answers
37
views
Devising a grammar for language L = { a^xb^ya^xb^y | x, y >= 0 }
I've been trying to come up with a proper grammar for this sort of language:
L = { aˣbʸaˣbʸ | x, y >= 0 }
I have failed to find a way to enforce consistent generation of terminals on either part (...
- 1
3
votes
2
answers
2k
views
Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form
Here's what Wiki says:
And here's what Mike Sipser says in his Introduction to Theory of Computation:
The problem arises when you try to read the two definitions - Mike Sipser seems to be suggesting ...
- 51
3
votes
1
answer
165
views
context-free shuffle for two-letter alphabets
The operation of shuffle takes two words and merges their symbols, keeping the symbols of each of the strings in the right order. It can be recursively defined by $x \parallel \varepsilon = \...
- 29.9k
0
votes
1
answer
110
views
CFG for the given language $L = \{~ a^\ell a^n b^m c^m d^n e^\ell ~|~ \ell,n,m \geq 0 \}$
I am writing this CFG to solve the problem:
$S \to ASBSC$
$A \to aAe ~|~ ε$
$B \to aBd ~|~ ε$
$C \to bcC ~|~ ε$
Is this correct or not?
- 1
0
votes
0
answers
16
views
step 2 of CFG conversion to Chomsky's normal form
in the step where you have to remove the epsilons, would you need to remove something like this:
A -> Bε
Or would you simply remove the ones that have epsilon by itself like this:
A -> ε
-1
votes
1
answer
50
views
The book says 27 terminals but I only see 10. Where are they?
On page 103 of Mike Sisper's Introdution to Theory of Computation, it says that the grammar has 27 terminals (26 being the letters of the English Alphabet and 1 being the space character) but in the ...
- 51
1
vote
0
answers
44
views
How to develop intuition to come up with Context Free Grammar?
So i'm taking this class automata and complexity at georgia tech and we were given practice material for our exam.
one of the question is to give context free grammar for these two languages
and the ...
- 11
0
votes
0
answers
36
views
What is the space complexity of deterministic real-time context-free languages?
The linear context-free languages are included in NL, and there exist linear languages that are NL-complete. On the other hand, the set of linear deterministic context-free languages is included in L. ...
- 1
0
votes
0
answers
53
views
Is there a way to modify the DK Test for DCFGs to test for ambiguity of CFGs?
I am currently reading Sipser's book on the Theory of Computation, and was wondering about the the question in the title.
Here is my current understanding of the concepts:
A deterministic context free ...
- 1