Questions tagged [context-free-grammar]

Context-free grammars give a set of rules for generating formal languages. The formal languages generated by a context-free grammar are known as context-free languages.

Filter by
Sorted by
Tagged with
0 votes
0 answers
18 views

Creating a context free grammar for this language. (Having difficulties keeping track of $3$ parts).

create a context free grammar that creates this language: $\{w_1bw_2bw_3 : w_1,w_2,w_3\in \{a,c\}^* \space\text{and}\space |w_2|+|w_3|<2|w_1|\}$ Usually when I solve context free grammar questions,...
user avatar
  • 2,051
1 vote
1 answer
38 views

Is DCFL closed with regular always?

Suppose $L=\{a^mb^n∣m≠n\}∪{(a+b)^∗b(b+a)^*a(a+b)^∗} =\{a^mb^n|m<n\} \cup \{a^mb^n|m>n\} \cup (a+b)^*b(a+b)^*a(a+b)^*$  It is DCFL ∪ Regular, hence it should be DCFL, but not able to design DPDA, ...
user avatar
-1 votes
0 answers
95 views

Prove that $L\subseteq 0^*$ is context free iff $L$ is regular.

Prove that $L\subseteq 0^*$ is context free if and only if $L$ is regular.
user avatar
-2 votes
1 answer
14 views

How to show $(L^+)^R$ = $(L^R)^+$ [closed]

I wanted to show that $(L^+)^R$ = $(L^R)^+$, I tried the following: $(L^+)^R$ = $L(L^*)^R$. But I don't really know how to continue. Also I'm not quite sure what the $+$ after the $(L^R)$ means. Is it ...
user avatar
0 votes
1 answer
31 views

How to prove that a language is not context-free using pumping lemma?

How could I realize this using the pumping lemma? What if the pumping part is between b and c or between a and b so that after pumping the word is still in L?
user avatar
0 votes
0 answers
44 views

Is it possible to create this context-free grammatic?

Is it possible to create this grammatic? $$ \left. 0^i 1^j 2^k \right| i + j \ne 2k $$ I try to create this, but I don't understand. I assume that we have to output $k$ characters '2' beforehand. But ...
user avatar
0 votes
1 answer
56 views

My proof of $\{a^p|p~~\mathbb{is~~prime}\}$ is not a CFL.

I want to show that the language $L=\{a^p~|~p~~\mathbb{is~~prime}\}$ is not a CFL. Assuming towards a contradiction that $L$ is a CFL. Let $p$ be the number from the Pumping lemma for context-free ...
user avatar
  • 656
0 votes
2 answers
36 views

Proof Attempt: non Context free languages and non regular language with some words added stay non regular/context-free.

Background: I was in class and heard this sentence from my professor "Well if you take a non context free language and add $2$ words to it then it will stay non context free". Now I was ...
user avatar
  • 2,051
0 votes
0 answers
43 views

Is there a s-grammar for $L_2=\{a^nb^m, n > m \ge 0\}$?

Peter Linz - An introduction to formal languages and automata (2001) third edition: A context free grammar $G=(V,T,S,P)$ is said to be a simple grammar or s-grammar if all its productions are of the ...
user avatar
0 votes
0 answers
14 views

CFG of $L=\{w \in \{a,b\}^* ~~|~~ \#_a(w)\ge \frac{|w|}{2} \}$

I want to find a CFG for the given language: $L=\{w \in \{a,b\}^* ~~|~~ \#_a(w)\ge \frac{|w|}{2} \}$ Is that correct: $$S \to ~~ aSb ~~|~~ bSa ~~|~~ aSbSa ~~|~~ aS ~~|~~ a ~~|~~ \lambda$$ Thanks!
user avatar
  • 656
0 votes
0 answers
74 views

How can I prove that L = {w ∈ {a, b, c, d} ∗ | #a(w) = #b(w) = #c(w) = #d(w)} is not context-free without using the pumping lemma?

I am stuck on this problem, I can prove it using the pumping lemma, but I'm wondering if I can also prove it using closure properties
user avatar
0 votes
0 answers
24 views

Is this a PDA for balanced parentheses language?

I have got following PDA: $A=(\{p, q\},\{0, 1\},\{Z\},\delta , p, Z)$ $\delta ( p, 0, Z) = \{(p, ZZ)\}$ $\delta ( p, 1, Z) = \{(p, \lambda)\}$ $\delta ( p, \lambda, Z) = \{(q, \lambda)\}$ Assuming ...
user avatar
  • 1
0 votes
0 answers
21 views

What does the ⇒ mean in Context Free Grammer? Also, how do I derive/get the L(CFG) from a CFG?

I'm a bit confused. Does the ⇒ simply denote you going through the CFG step by step ? To use a pretty basic-ish example: sentence ⇒ subject | predicate subject ⇒ article | noun predicate ⇒ verb | ...
user avatar
  • 11
0 votes
1 answer
78 views

On the general relationship between automata, expressions, and grammars

When I took Theory of Computation, the main points of interest were three kinds of automata: finite, pushdown, and Turing, one type of expression: regular expressions which are equivalent to finite ...
user avatar
0 votes
1 answer
44 views

Convert a CFG to GNF

I have to convert the below grammar to GNF. $S \Rightarrow SA$ $A \Rightarrow aAb|cCc$ $B \Rightarrow D|ba$ $C \Rightarrow dCd| ɛ$ $D \Rightarrow De|Df|cD|c$ I have seen some examples and tutorials on ...
user avatar
1 vote
1 answer
32 views

Solution Verification: Suggest a context-free grammar that creates this language.

Suggest a context-free grammar that creates this language: $L=\{tct^Rcscw | t,s,w\in (a+b)^*, \space\space s \ne w^R\}$ My Solution Approach: We split the language to $S_1$ and $S_2$, where $S_1$ ...
user avatar
  • 2,051
0 votes
2 answers
53 views

Find a CFG for all the binary strings in which the characters in $i$ and $i + 2$ positions are same, and the length of the string is at least 2.

I have homework which is about CFGs, their simplification, and their normalized forms. I have also seen some examples on the internet, but unfortunately, I could not solve the below question. All the ...
user avatar
0 votes
1 answer
57 views

Writing a grammar that creates a specific language from a given grammar in Chomsky normal form

Given a grammar in Chomsky normal form that creates a language $L$ over alphabet $\Sigma$, that the letter z doesn't belong to $\Sigma$, without the empty string. I need to write a context-free ...
user avatar
0 votes
1 answer
39 views

Pumping lemma: if you pump to $uv^0wx^0y$, wouldn't $|vx| \ngeq 1$?

For pumping lemma for CFLs, for strings $s$ in $L$, they follow the form $s = uvwxy$ and $|vwx| \leq n$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for $i \geq 0$. If I want to prove a language is not CFL, ...
user avatar
  • 1,713
1 vote
2 answers
71 views

Failure of context-free pumping lemma of $a^nb^n$

I know $a^nb^n$ with $n\geq0$ is considered a context-free language, but if I try: Using pumping length $p = 3$ $n = p$, thus we have $aaabbb$ $u =aa$ and $y = bb$ $v = a$, $w = b$ and $x=λ$, then $|...
user avatar
0 votes
1 answer
35 views

Converting Grammar to Chomsky Normal Form

I have to convert a grammar to Chomsky normal form, the grammar is something like this (not exactly but this is the important bit) V → W W → wWxXyYzZ | vXy | xX X → xYZ | xY | xW | zZ Y → xX | wW | wV ...
user avatar
2 votes
1 answer
55 views

CFG for $\{0^i1^j0^k\mid i+2j=3k\}$

Edited: I try to find a Context-Free grammer for $\{0^i1^j0^k\mid i+2j=3k\}$ as follow \begin{align*} S&\to 000S0| 111B00| 01B1| 001B1|\lambda\\ B&\to 111B00| \lambda \end{align*} But ...
user avatar
  • 21
0 votes
0 answers
34 views

Prove the language of equal a's and b's or b's and c's is inherently ambiguous

Question from Sipser, exercise 2.29. Prove that the language $A = \{a^ib^jc^k | i = j \text{ or } j = k \}$ is inherently ambiguous, that is, every grammar which generates $A$ is ambiguous. So the ...
user avatar
0 votes
1 answer
44 views

How do you show that the language $L= \{ a^nb^nc^na^kb^lc^m \mid l,m,n \geqslant 0 \text{ and } k >0 \}$ is not context-free.

This is somewhat similar to another question I asked here. In that case you could apply the pumping lemma by pumping down on $a^nb^nc^nabc$ . However when $>$ is replaced by $\geq$ for all $\{k,l,m,...
user avatar
  • 1,918
1 vote
2 answers
38 views

Constructing grammar for $a^ib^j$ / $i\neq j$

I want to construct a grammar for the following regular expression: $a^ib^j / i \neq j$. I did it the following way: $S_1 \rightarrow aaSb | aaAb$ $A \rightarrow aA | \epsilon$ $S_2 \rightarrow aSbb | ...
user avatar
2 votes
0 answers
26 views

constructing grammar for 1*0*1(1+0)*

I want to construct a grammar for the following regular expression: $1^*0^*1(1+0)^*$. I did it the following way: $S \rightarrow AB1C$ $A \rightarrow 1A | \epsilon$ $B \rightarrow 0B | \epsilon$ $C \...
user avatar
1 vote
1 answer
39 views

Induction on automaton [closed]

Let an automaton defined by the following transition table: 0 1 $\rightarrow$A A B $\leftarrow$B B A I have this finite automaton, and it recognizes the languages with only an odd number of $1s$ ...
user avatar
0 votes
0 answers
12 views

Finding S-Attributed Grammar

Finding S-Attributed Grammar Given a grammar: L -> id LT LT -> , L LT -> ε My attempt: L -> LT LT -> id, L, ε From my understanding, an S-attributed grammar is "bottom-up" so ...
user avatar
0 votes
1 answer
28 views

Proof of context free Language

$$L:=\{w\in\{a, b, c\}^*| ∃ i, j ∈ N :w = a^i⋅b^i⋅c^j ∧ i < j\}$$ I am trying to prove/disprove that this is context free. I was sure this was not context free, since there are 3 pumping operations,...
user avatar
4 votes
1 answer
121 views

Finding Context Free Grammar for a language

I was trying to find the CFG for the language below. However, I couldn't do that. Can anyone help with this problem? $$\{1^n 0^m 1^k 0^p | n \geq 2, m,k,p \geq 1, n+k = m+p\}$$
user avatar
1 vote
1 answer
37 views

Find a CFG for all words that can be obtained in the form $a^ib^{i+k}a^k$

Find a CFG for all words that can be obtained in the form of $a^ib^{i+k}a^k$ where $i,k\ge1$. This is what I have so far: $$ S\to aXa \\X\to bXB \mid bb $$ I understand that number of b's must be ...
user avatar
  • 13
1 vote
1 answer
54 views

Why is {$0^𝑛 1^𝑛 : 𝑛≥0$} context free?

This Language {$0^𝑛 1^𝑛 : 𝑛≥0$} is context-free as per another answer I read on this site. Link: What does it mean to say a language is context-free? For this example take S = $0^p 1^p$ However, if ...
user avatar
0 votes
0 answers
27 views

Prove that grammar in Chomsky form is equivalent to it's original form

I have a grammar $G_1$ in the following form: $$ S \rightarrow bA|aB$$ $$ A \rightarrow bAA|aS|a$$ $$ B \rightarrow aBB|bS|b$$ Chomsky's form of the grammar ($G_2$): $$ S \rightarrow CA|DB$$ $$ A \...
user avatar
  • 253
1 vote
1 answer
47 views

CFG with even length and not in the form of SS.

I know that we can construct a CFG of all strings over $\{0, 1\}$ with even length using the following $$T \mapsto 0T0 \mid 0T1 \mid 1T0 \mid 1T1 \mid \epsilon$$ But I want the string to have non-...
user avatar
  • 407
0 votes
1 answer
44 views

What are general tips for generating grammars for context free languages?

Perhaps, this does not have a "correct" answer, but what are general tips for creating context free grammars for context free languages? I know there is usually no step by step solution to ...
user avatar
0 votes
1 answer
32 views

Syntax diagram confusion

Have a look at the syntax diagram for the escape language: I read the second set of transitions as follows: The state transitioned to by the \ symbol can ...
user avatar
  • 173
1 vote
1 answer
74 views

Context Free Grammar for strings of $z^n$y$x^m$ $w^n$

I am trying to make a context-free grammar that generates all the strings in the language: $\{z^nyx^mw^n : m,n \ge 0\}$. Right now for my rules I have: $S\to yX$ $S\to y$ $X\to e$ $X\to xX$ $S\to zXSw$...
user avatar
1 vote
2 answers
175 views

Decidability of DCFL and Undecidability of CFL with respect to regularity

I synced with this Hendrik Jan's answer that to prove undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and ...
user avatar
0 votes
0 answers
30 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 \;...
user avatar
  • 536
0 votes
0 answers
31 views

Converting a CFG to Chomsky Normal Form with 5 steps

I'm learning how to convert from CFG to Chomsky Normal Form and I'm having problems with this exercise Converting a CFG to Chomsky Normal Form `` A→BAB|B|ɛ; B→00|ɛ ...
user avatar
0 votes
1 answer
60 views

Combination of 2 context free grammars

I am required to show that the language $L$ is context-free where $$L = \{q_1q_2 \dotsm q_nt_1t_2 \dotsm t_n \mid q_i \in Q, t_i \in T, n \geq 0 \}$$ where $Q$ and $T$ are context-free languages. I ...
user avatar
  • 36
-1 votes
1 answer
45 views

Is $a^n b^n$ context free even if we take strings instead of characters?

Let a and b be 2 strings . Does the set {$a^nb^n$ , $n\geq0$} still form a context free language? Intuitively, I feel that should be the case since in this case I'm just storing strings instead of ...
user avatar
  • 36
0 votes
1 answer
809 views

How to design a regular language that accept all binary string except for string that contains one specific occurrences?

Good day, I come across this question on my textbook and would like to seek some help. In this question, I was asked to design a regular language that accept all binary string except for string that ...
user avatar
1 vote
2 answers
127 views

proof / disproof of context-free language

Given the following language: $$ L = \{b^n \mid \text{$n$ is prime} \}\cup \{b^n \mid \text{$n$ is even}\} $$ Need to proof or disproof whether this language is context-free or not. I know that only ...
user avatar
  • 33
0 votes
1 answer
106 views

CFG: Translate English sentence to math basic logic

I need help making sure the notations below matches the English sentence. $X_i$ is called an instantiated node in its definition below: Given a derivation of some context free grammar: $D = \...
user avatar
  • 991
1 vote
1 answer
70 views

Is there really a proof that all context-free grammars can be parsed using a LL(1) grammar without backtracking?

I was watching a youtube video on a parsing library that I have an interest in that you can find here: https://www.youtube.com/watch?v=wreCg30pyts&t=1272s. What is interesting though is that at 30:...
user avatar
0 votes
0 answers
42 views

Pumping Lemma proof for this language: $L= \{a^ib^jc^{ij} \mid i, j \geqslant 0\}$

i have troubles to show that this language is not context free with the pumping lemma. As a word I chose: $a^mb^mc^{m^2}$ I solved all the cases but one, which is: "$vy$ contains $b$'s and $c$'s&...
user avatar
0 votes
0 answers
36 views

How can I construct a context-free grammar if the number of 1's is a multiple of the number of 0's?

Suppose I have a language such that L = {w | w is the string 0n1m where m is a multiple of n}. I am told that a string like this would be considered a context-free language. Definitionally, some ...
user avatar
3 votes
1 answer
355 views

How would you define "twice as many" when 0 is concerned?

Consider the statement that "$\mathscr{L}$ is defined as a language where all strings contained in it contain twice as many b's as a's." Clearly a string containing a single a will yield two ...
user avatar
0 votes
1 answer
41 views

Do we always need to add a new start symbol when converting to Chomsky Normal Form?

I understand that when converting a CFG to a CNF that we need to add a new start symbol if the start symbol occurs on the right-hand side. For instance, this grammar is converted like such: $$S\...
user avatar

1
2 3 4 5
19