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
0 answers
10 views

Can the leaf nodes of a parse tree be labeled by a variable, a terminal, and the empty symbol; or only a terminal and the empty symbol?

When you are deriving a string using a context-free grammar (CFG), you start with the start symbol and at the right side you have combinations of variables (non-terminals) and terminal symbols. Let's ...
user avatar
  • 337
-2 votes
0 answers
23 views

How to use Pumping Lemma $L = { wsw | w ∈ {0,1}*, s ∈ {2}*, and |w| = 2 * |s| }$?

I'm trying to use the Pumping Lemma to prove that $L = { wsw | w ∈ {0,1}*, s ∈ {2}*, and |w| = 2 * |s| }$ is not a CFL.
user avatar
-2 votes
0 answers
24 views

How to use Pumping Lemma for L={www|w∈{0,1}* and w starts with 0}?

I know my question might be a bit similar to How to use Pumping Lemma for $L = \{www | w∈\{0,1\}^*\}$ However, I feel that it is different enough due to the extra requirement of starting with 0
user avatar
-2 votes
1 answer
42 views

proof that every sentence obtainable by left-most derivations only when Greibach normal form

Could someone help me prove the following statement: “For any grammar in Greibach normal form, every sentence is obtainable by left-most derivations only.” I see that this is trivial, but I can't ...
user avatar
1 vote
1 answer
67 views

How are regular languages not structurally recursive?

This blog posting states that "regular languages aren't structurally recursive" while "That's not the case for context-free grammars" In what sense is the term "structurally ...
user avatar
1 vote
3 answers
131 views

How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?

I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL. Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$. When I separate to cases, ...
user avatar
  • 241
1 vote
1 answer
36 views

substitution of same variable in context-free grammars

Above is a theorem coming from the book "Formal languages and automata" by Peter Linz concerning substitution of variables. Could someone explain why A and B have to be different variables?
user avatar
-2 votes
1 answer
41 views

Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?

Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$ Why is $L'$ a regular language? I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
user avatar
  • 241
1 vote
1 answer
74 views

variable repetitions in pumping lemma for context-free languages

Above is the proof of the pumping lemma for context-free languages, coming from the book 'Formal Languages and automata' by Peter Linz. The picture below is in support of the proof. I do not ...
user avatar
0 votes
0 answers
15 views

Regular, CFL, non-CFL infinite closures [duplicate]

I was wondering about infinite closure properties. Are the Regular languages closed under infinite union? Infinite intersection? Probably not, by taking $\forall n>0~~L_n=\{a^nb^n\}\in RL$, then $\...
user avatar
  • 241
3 votes
4 answers
2k views

Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?

Why is $L=\{w \mid ~|w|\bmod3=\#_a(w)\bmod3\}$ a regular language? $\#_a(w)$ is the number of $a$'s in $w$. So far every language that I saw containing modulo was a ...
user avatar
  • 241
0 votes
0 answers
29 views

How to show that $\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL? [duplicate]

I want to show that the language $L=\{a^p ~|~ p\text{ is not prime}\}$ is not a CFL. If I look at $\bar{L}=\{a^p ~|~ p\text{ is prime}\}$, it is pretty straightforward to show that it is not a CFL ...
user avatar
  • 241
0 votes
0 answers
12 views

How to determine whether a CFG produces the null set? [duplicate]

I came across this CFG G(V,Σ,R,S): V = {0,1,A,B,C,S} Σ = {0,1} R: S->ABCS A->AA|ε Β->bBb|ε C->cC|ε It seems obvious to me that it generates no (finite ...
user avatar
2 votes
1 answer
36 views

Why is $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$ regular?

Why is this language regular: $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$? Where $\#_a(w)$ is defined as the number of $a$ in $w$. Isn't that a concatenation between 2 CFL? Thanks!
user avatar
  • 241
1 vote
1 answer
42 views

is there a non-context free language A such that A1 is context free?

Is there a non-context free language A over the alphabet $\{0,1\}$ such that $A1 := \{a1 : a\in A\}$ is context free? I was thinking of the language $A = \{0^n 1^{n-1} : n > 0\}.$ Unfortunately, ...
user avatar
1 vote
1 answer
32 views

Is $\{x2y : |x| = |y|, x\in A, y\in\{0,1\}^*, d(x,y) = k\}$ context-free for some infinite regular language $A$?

For two equal-length binary strings $x$ and $y$, let $d(x,y)$ denote the Hamming distance. Prove or disprove: there exists a positive integer $k$ such that the language $\{x2y : |x| = |y|, x\in A, y\...
user avatar
0 votes
0 answers
37 views

If two states of a DFA are k-equivalent and k+1 equivalent

Let $p,q$ be two states of a DFA, such that $p\equiv_kq$ and $p\equiv_{k+1}q$. Does it mean that $p\equiv q$ ? I don't think so, because if the minimization algorithm can continue, they might be ...
user avatar
  • 241
0 votes
1 answer
48 views

Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language

Suppose o is a map on strings to strings. For every language R, we let $o(R) := \{o(x) : x \in R\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the ...
user avatar
0 votes
3 answers
127 views

Find a Context-Free Grammar for $L = \{a^wb^xc^yd^z | w + x = y + z\}$

I have to find a CFG for the given expression: $L = \{a^wb^xc^yd^z | w + x = y + z\}$ This is what I've tried so far: S -> aSd | B | ϵ B -> bBc | ϵ It works for expressions like: aabcdd, ...
user avatar
1 vote
1 answer
40 views

If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular

Prove/disprove the following claim: If $L\in RL$ then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\} \in RL$ I think that this is true, and my intuition is by using $L_{pq}$ s.t: For every $(p,q)\in Q\times Q$...
user avatar
  • 241
1 vote
3 answers
173 views

How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language

Let $L$ be a regular language. Define: $half(L)=\{x|xy\in L,|x|=|y|\}$ Prove that $half(L)$ is regular as well. I have seen a hard proof by using the DFA A of L, building a NFA B (such that every ...
user avatar
  • 241
3 votes
1 answer
80 views

Are the set of all Bitcoin addresses a context-sensitive language?

This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language&...
user avatar
1 vote
2 answers
75 views

Prove or disprove that the language $L = \{xcy\, | \, x,y\in \{a,b,c\}^\star, |x|_a = |y|_b \}$ is context free

Let me cross post my question from math.stackexchange, since I feel this community is more related to the field. Title is self explanatory. I want to know is the language $L = \{xcy \,| \,x,y\in \{a,b,...
user avatar
  • 121
0 votes
2 answers
83 views

CFL with regular substitution to make a regular language

If I have a CFL, can I define a regular substitution to make it a RL? For example, if I have the language $\{a^nb^n \mid n\ge0\}:$ Define $h(a)=a$ , $h(b)=b$, then $h(L)={a^*}$ , am I right? Thanks!
user avatar
  • 1
-1 votes
1 answer
64 views

prove $A$ is context-free

Prove that the following language is context-free by giving a context-free grammar that generates the language: $A = \{a \in \{0,1\}^* : \text{ no character in an even position is a 0 or no character ...
user avatar
-1 votes
1 answer
72 views

Possible PDA for $ L = \{ a^{3n}b^{2n} | n \ge 0 \}$ without transforming CFG to PDA

To those of you who saw my post from an hour ago - I deleted it because I came up with an idea. To summarize, I have to design a PDA for this language, without using the usual method of firstly ...
user avatar
  • 155
1 vote
1 answer
57 views

Designing a PDA without using CFG -> PDA for the language $ \{ a^nb^m | n \le m \le 2n \}$

$L= \{ a^nb^m | n \le m \le 2n \}$ As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to ...
user avatar
  • 155
0 votes
1 answer
51 views

CFG to RG Conversion

I'm struggling with this question. I would appreciate a detailed solution as it would help me better understand the subject. Convert the following Context Free grammar into a Regular Grammar: S -> ...
user avatar
-4 votes
1 answer
40 views

show that $L=\{a^*\}\cup\{b^ja^{n^2}|0<j,1\leq n \}$ Holds the pumping lemma for context-free languages

prove this language verifies the conclusion of the pumping lemma show that $L=\{a^*\}\cup\{b^ja^{n^2}|0<j,1\leq n \}$ Holds the pumping lemma for context-free languages the problem is that I ...
user avatar
-2 votes
2 answers
45 views

Context free grammar for $a^i b^j a^j b^i$

I recently started learning context free grammars and was working on a couple of exercise problems and couldn't really figure out how would this exactly look like. I started with: $$\begin{align}S&...
user avatar
  • 1
0 votes
1 answer
43 views

Determine the type of $L=\{w:|w|\text{ is even, and it has }\frac{|w|}2\text{ consecutive 0's}\}$

I've been solving a lot of questions lately about determining the type of a given language, by type I mean whether it's regular, CFL, in P, Turing-decidable, Turing-acceptable, or all the languages. ...
user avatar
2 votes
0 answers
68 views

Is the language $L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ context-free?

$L = \{{a^{2n+1}b^{m+2}a^n | m \neq 2n}\}$ I tried to split $L$ in 2: when $m > 2n$ and $m<2n$, however both resulting languages are not context-free, so I did not find out anything about $L$. ...
user avatar
-3 votes
1 answer
90 views

Prove a stronger version of the pumping lemma for context-free languages

Let $L$ be a context-free language. Prove that there exists integer $p>0$ such that $ \forall z\in L $ such that $ |z|\ge p $, there exists a partition $ z=uvwxy $ such that $|vwx|\le p$ $|vx|\...
user avatar
1 vote
1 answer
76 views

Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?

$L=\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ I tried writing $L$ as the union of the language created with $j$ odd and the one with $j$ even. When $j$ is ...
user avatar
  • 11
0 votes
2 answers
74 views

Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones

$L=\{ w \in \{ 0,1 \} \}$ where $w$ contains at least three ones Here is one solution for the productions: $S \to A1A1A1A$ $A \to 1A | 0A | \epsilon$ However, now I have a question. Could I modify the ...
user avatar
  • 155
1 vote
1 answer
79 views

How to create all even length words from a given CNF grammar

given CFG G1 = {V1, Σ1, R1, S1} in its CNF form, I have to define a new G5 grammar that constructs L(G5) using {V1, Σ1, R1, S1}: while L(G5) = { x ∈ L(G1) | |x| is even } i . e . L(G5) composed of all ...
user avatar
  • 11
0 votes
1 answer
85 views

Context-free grammar for language $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$ [duplicate]

I need to find the production rules for the following language: $L = \{u \in \{a, b\}^* \mid |u|_a = |u|_b\}$ Well, the first thing I could come up with is $S \to aSb | \epsilon$ But this only covers ...
user avatar
  • 155
0 votes
0 answers
37 views

Union of two context-free grammars and their productions

Is it possible to create an union of two context-free grammars? I found a PDF material from the university of Iowa where they claim that it's possible but I just don't know how. They had that for ...
user avatar
  • 155
1 vote
1 answer
71 views

Context-free grammar for $L=\{ a^nb^m | n \le m+3 \}$

I'm having problems determining the productions for a CFG describing the language $L=\{ a^nb^m | n \le m+3 \}$ where $n,m \ge 0$ I'm very new to this so this example might be a little harder, but ...
user avatar
  • 155
1 vote
0 answers
21 views

Relation between left derivations, right derivations and number of parse trees?

I saw this question on a test-prep site Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees? ...
user avatar
0 votes
0 answers
16 views

Can you a push multiple symbols on simplified PDA stack in one transition?

I encountered this problem when I was converting a PDA to a CNF and I was looking for two transitions that push and pop the same symbol(one pushes and one pops). The PDA I was converting had this ...
user avatar
  • 61
2 votes
1 answer
69 views

prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free

Given that $\#\notin \Sigma$ and $L\subseteq \Sigma^*\#\Sigma^*$, prove that if $L$ is context-free language then $L' = \{w_2\#w_1 \mid w_1\#w_2\in L\}$ is context-free. I'm trying to prove this in ...
user avatar
2 votes
1 answer
40 views

Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal

I want to construct a context-free grammar for this language: \begin{align*} L = \{uc^nd^nv\mid \ u,v \in \{a,b\}^* \text{ and the number of a's and b's in } uv \text{ are equal}\} \end{align*} I know ...
user avatar
3 votes
0 answers
32 views

Is there an alternative for the formal language theory that could be used for flowchart diagrams?

I am creating a tool for validating, parsing and interpreting flowchart diagrams on diagrams.net, and it is neccessary to give users an opportunity to define a set of rules for the diagram. So, in the ...
user avatar
0 votes
1 answer
20 views

Construction of a Turing Machine that accepts the language of (a^nb^nc^md^m for) m,n >= 1

i recently have been practicing constructing Turing Machines for languages. But i can't seem to figure this one out. I've seen a few videos on constructing 3 equal length strings (a^nb^nc^n) But i can'...
user avatar
0 votes
2 answers
199 views

How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$

We know that $L = \{ xy | x, y \in (0 + 1)^*, |x| = |y|, x≠y\}$ is context free. But my question is how we check $x ≠ y$ in $PDA?$ For example $x=0^n1^n$ and $y=1^{2n}.$ We can easily draw $PDA$ by ...
user avatar
  • 1
0 votes
1 answer
82 views

How to prove ww^r is context free using pumping lemma for context free languages

I am having a hard time to prove it, what i know is we cannot prove that a language is regular by using pumping lemma cause even if the "pumped string" is in the language the language could ...
user avatar
3 votes
2 answers
1k views

Is this language a context-free language or not?

I try to determine if the following statement is true: for any given language $L \subseteq A^*$ if $L$ is a context-free language then $L_1 = \{u^Rv^R \ | \ uv \in L, |u|=|v| \}$ is also a context-...
user avatar
  • 55
0 votes
1 answer
34 views

When is a grammar ambiguous or When is a grammar not ambiguous?

I was looking at an example of grammar from the website: grammer example which is as follows: S → aB / bA S → aS / bAA / a B → bS / aBB / b I believe they forgot to write: A -> a Next, we are going ...
user avatar
8 votes
1 answer
694 views

Conjecture: a half of a pairing context-free language must be a regular language

If $A$ and $B$ are languages, let $A\bowtie B$ denote the set of strings made by concatenating any word from $A$ and any word from $B$ of equal length. $$A\bowtie B \equiv \{ ab : a\in A,\;b\in B, |a|=...
user avatar

1
2 3 4 5
32