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
1 answer
14 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 ...
hl037_'s user avatar
  • 101
0 votes
0 answers
26 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 ...
John Daniels's user avatar
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 ...
John Daniels's user avatar
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 ...
John Daniels's user avatar
-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 ...
user164478's user avatar
-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}
user164478's user avatar
1 vote
2 answers
366 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 ...
Miki's user avatar
  • 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?
slm cmm's user avatar
2 votes
2 answers
51 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 ...
cpf9231's user avatar
  • 21
0 votes
1 answer
29 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. ...
Addem's user avatar
  • 315
0 votes
1 answer
57 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 ...
Aum Thakkar's user avatar
-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 |...
Jonah's user avatar
  • 1
0 votes
0 answers
52 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 ...
Tanuj's user avatar
  • 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?
user1868607's user avatar
  • 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$ ...
user163802's user avatar
-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 ...
bipartite's user avatar
0 votes
1 answer
59 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 ...
empty-search's user avatar
1 vote
0 answers
30 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 ...
Chris_F's user avatar
  • 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,...
wsz_fantasy's user avatar
1 vote
1 answer
171 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 ...
Max Azatian's user avatar
0 votes
0 answers
27 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. ...
Priit's user avatar
  • 1
1 vote
1 answer
72 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?
oleshkowitz's user avatar
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),...
pezbecoding's user avatar
1 vote
1 answer
52 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 ...
Keroten's user avatar
  • 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 ...
emma's user avatar
  • 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 ...
user69507's user avatar
-1 votes
1 answer
173 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 ...
Lorenzo's user avatar
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 ...
Stanley's user avatar
  • 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\...
user8718165's user avatar
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$ ...
RookieCookie's user avatar
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)\; \...
dvox's user avatar
  • 13
0 votes
0 answers
24 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.
aassegai's user avatar
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.
Peter Golfplatz's user avatar
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 ...
tafelwasser123's user avatar
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 ...
phuck's user avatar
  • 1
0 votes
0 answers
51 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 ...
Zoha Javed's user avatar
0 votes
0 answers
47 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: ...
whoAsked's user avatar
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 ...
Hiefenhoomer's user avatar
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 (...
MWR_'s user avatar
  • 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 ...
Sbeve's user avatar
  • 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 = \...
Hendrik Jan's user avatar
  • 29.8k
0 votes
1 answer
106 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?
Yousaf's user avatar
  • 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 -> ε
joao pereira's user avatar
-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 ...
Sbeve's user avatar
  • 51
1 vote
0 answers
43 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 ...
SkV's user avatar
  • 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. ...
Andres's user avatar
  • 1
0 votes
0 answers
50 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 ...
Coziyu's user avatar
  • 1
0 votes
0 answers
13 views

When finding the CNF of a CFG, in the step where you eliminate unit productions, does order matter?

Suppose a CFG has unit productions A -> B and C -> D among other productions, possibly involving ...
Addem's user avatar
  • 315
1 vote
2 answers
80 views

Need to create CFG that requires sum of other letters

I have a homework assignment that requires me to create CFG $G$ for $$L = \{a^i b^{i+j+k} c^j d^k\}$$ so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
Sefa Kalkan's user avatar
2 votes
0 answers
95 views

How to write a grammar with a low-precedence unary postfix operator?

Like this person on Google Groups, I'm trying to understand how to write a grammar involving Wolfram Language's low-precedence unary & operator. The operator ...
ForceBru's user avatar
  • 121

1
2 3 4 5
34