Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
26 views

Closure of regular languages to $A(L)=\{zyx|x,y,z \in \{0,1\}^*, xyz \in L\}$

Given: $A(L)=\{zyx|x,y,z \in \{0,1\}^*, xyz \in L\}$ Given $L \subseteq\{0,1\}^*$, Prove/Disprove: If $L$ is regular $\implies$ $A(L)$ is regular If $L$ is context free$\implies$ $A(L)$ ...
2
votes
1answer
134 views

prove/disprove: If the language $L$ is such that for every $CFL$ $L'$ , the language $L \cap L'$ is $CFL$, then $L$ is regular?

Hey guys I got this question in my homework and I can't figure out what to do: If the language $L$ is such that for every $CFL$ $L'$ , the language $L \cap L'$ is $CFL$, then $L$ is regular? I sat ...
0
votes
0answers
44 views

what is the mapping reduction of $A_{TM}$ to $\overline{CF_{TM}}$

first post here :) I am trying to find a reduction from $A_{TM}$ to $\overline{CF_{TM}}$. definitions: $CF_{TM}\:=\:\left\{<M>| M\:is\:a\:TM\:and\:L\left(M\right)\:is\:a\:context-free\:...
0
votes
0answers
20 views

Proving Turning Decidable's

Prove that L CFG \ L RG is Turing-decidable, where L CFG = {< G, w > G is a CFG that generates string w}. L RG = {< G, w > G is a regular grammar that generates string w} In relation ...
0
votes
0answers
19 views

Generating context-free grammar from language

I need to give a context-free grammar for each of the examples: $L_1=\{a^hb^ka^mb^n ~~ \colon ~~ h + k = m+ n\}$ $L_2=\{a^ib^ja^k ~~ \colon ~~ (i = j ~~and~~ k \ge 0)~~or~~(i\ge0~~and~~j > k)\}$ ...
0
votes
0answers
10 views

Which string in this context free grammar shows that the CFG is ambiguous?

I have the CFG with the production S: S → SS ∣ ab ∣ a I need to prove that this CFG is ambiguous. I'm having trouble finding a string suitable that will prove its ambiguity. I've constructed parse ...
0
votes
0answers
9 views

Is there anything in the literature about $2k$-nary infix grammars, in particular easy validity and parsing schemes?

Suppose $k$ is a positive integer: I'm working with the $2k$-nary infix grammar $$ S \to \mathrm{opd}\ |\ SS\ldots S\ \mathrm{opr}\ SS\ldots S, $$ where there are $k$ $S$s in each side of the $\mathrm{...
0
votes
0answers
23 views

build context free grammar

build context free grammar generating language $$[a^n{b^3}^ma^5b^3{{{c^2}^n}^+}^m],|n>0,m>0$$ Hey ,first off all sorry for my english :) My problem is ,that i can't understand principle and ...
1
vote
1answer
28 views

concatenation of 2 non-context-free languages that is context-free but not regular

I'm having today a test on formal language theory, and I've seen a question about it I'm having hard time solving. The question is: Give an example of 2 languages, L,M which are non-context-free but ...
2
votes
2answers
52 views

context free language prove or disprove

I have to prove or disprove that for every language $L$ which has the properties: for every non-prime length there is at least one word in L. for every prime length none of the words are in L. is ...
1
vote
1answer
30 views

How to disprove that the union of all non-context-free languages over $a$ is also non-context-free language?

This is the proof I came across: $L=\{a^{x^j}|j\ge 0, 2\le x\in \mathbb N\}$ is a non-context-free language. Suppose otherwise, then let $n$ be the constant promised in the pumping lemma. Let's ...
1
vote
1answer
22 views

How to transition from context-free grammar $G$ to to context-free grammar which starts and ends with specific letters?

Given context-free grammar $G$ whose terminal letters are $\{a,b,c,d\}$ how can we transition to context-free grammar which contains the words from the language that $G$ creates but which start with $...
-1
votes
1answer
49 views

Regular Grammar

Devise a regular grammar in normal form that generates the language L. Let L be the language consisting of all binary numbers divisible by 4. I know the different aspects needed to be generated: ...
0
votes
1answer
50 views

Pumping Lemma - unregular expression

How do prove that this expression is unregular, I know firstly you have to try prove that it is regular and work from there. I also know that $w=xuz$ and the three rules are needed Let $M$ be the ...
0
votes
0answers
40 views

Context-Free grammar - Normal form

Termials = a,b,c. non-Termials = A,S. Production Rules: (1) S → aS (2) S → bA (3) A → bA (4) A → cA (5) A → c (6) S → a How do you write the following in normal form, I understand that it is ...
0
votes
1answer
51 views

Formal Languages - Context Free Grammar

Describe the formal language over the alphabet { a,b,c } generated by the context-free grammar whose non-terminals are 〈 S 〉 and 〈 A 〉 , whose start symbol is 〈 S 〉 , and whose production rules ...
0
votes
0answers
9 views

Is L = { αγβ | α, β ∈ {a, b}* & γ ∈ {a, b}*1{a, b}* & |α| = |β| ≥ |γ| } context-free?

L = { αγβ | α, β ∈ {a, b}* & γ ∈ {a, b}1{a, b} & |α| = |β| ≥ |γ| }. So i need to find a contex-free grammar for L ? The thing is, i am not sure how to start. I belive I need to simplify the ...
1
vote
1answer
29 views

If a language and its complement are context-free, is it regular?

If both $L$ and $\overline{L}$ are context-free, is $L$ necessarily regular?
1
vote
1answer
25 views

How to design a Context-Free Grammar and Pushdown Automaton for the following language

How would you design a context-free grammar for the following language? $$ L = \{a^{(n^3+1)}\mid n \geq 1\} $$ And derive a Pushdown Automaton that accepts the same language. Any help given would be ...
0
votes
0answers
37 views

Verification of “Prove/Disprove that the language $L = \{ a^kba^{2k}ba^{3k} | k \geq 0\}$ is context free.”

I attempt to show that the language $L = \{ a^kba^{2k}ba^{3k} | k \geq 0\}$ is not context free by applying the Pumping lemma for context-free languages. This is achieved by a proof by ...
0
votes
0answers
242 views

Need a PDA for L={ a^n b^m c^m d^n n,m>=1 }

I am trying to desing a PDA for automata lecture.Language is L={ a^n b^m c^m d^n n,m>=1 } ...
1
vote
1answer
55 views

Model BNF Formally in mathematical terms

Usually, a language is formally defined as some subset $L$ of the Kleene-closure $\Sigma^*$ of some "alphabet" (i.e. finite set) $\Sigma$, where by Kleene closure we mean the infinite union $$\Sigma^* ...
1
vote
1answer
30 views

Language contex-free

$$L=\{a^kb^nc^md^t\mid n+m=2(k+t)\}.$$ So I am trying to figure out if this language is CFL. So trying to prove that it is not CFL with the pumping lemma, I am not getting anywhere (using the word $a^...
0
votes
1answer
31 views

Is $L_4$ a CFL?

Consider the following language: $$L_4 = \{a^ib^jc^kd^l : i,j,k,l \ge0 \wedge i=1 \Rightarrow j=k=l\}.$$ Prove or disprove: $L_4$ is a context-free language. To me, it looks like $L_4$ can be ...
0
votes
1answer
33 views

Language contex-free or not?

I was wondering whether this language is context-free or not? It's $L = \{ AB ~|~ |A| = |B| \text{ and } A \neq B \}$ . The alphabet is $\{ a, b \}$. In my textbook it's written that it is ...
0
votes
1answer
36 views

What would be the complement of $L =\{a^{n}b^{m}a^{n}b^{m} | n,m \geq 1\}$

I understand the complement of L would be all the strings not in L, but I'm having a hard time writing down the structure of all the strings not in L.
0
votes
0answers
24 views

How to prove that $L=\{a^kb^mc^{m-k}|m\ge k\ge0, m-k\ge k\}$ is not context-free language?

Prove that $L=\{a^kb^mc^{m-k}|m\ge k\ge0, m-k\ge k\}$ is not context-free language. We can suppose by contradiction that $L$ is context-free and choose $Z=a^kb^{2k}c^k$. Using pumping lemma, $vwx$ ...
0
votes
1answer
54 views

Convert this grammar to language

I want to convert the following grammar to language but I am not able to think and answer. $$S \to aSa \mid bSa \mid ab \mid ba$$ It gives me a lot of choices when I tried building its derivation ...
0
votes
0answers
22 views

Can redundant variables be removes in transition to Chomsky normal form grammar?

I have the following context-free grammar: $$ S\to aAb|aaBb|ab\\ A\to S|B\\ B\to C|S\\ C\to aC $$ and I need to convert the grammar to Chomsky normal form (CNF). After removing unit rules I get: $$ S\...
0
votes
1answer
43 views

Is $L = \{a^{i+j}b^{j+k}c^{i+k} | i,j,k > 0\}$ context free?

This is not an assignment question. Professor gave this for us to think about. I want to say its not context free since in the case $i=j=k$ then we have the language $a^nb^nc^n$ which we know is not a ...
0
votes
1answer
22 views

On left recursive context-free grammars

Definition Context-free grammar $G$ is said to be left-recursive, if there exists such non-terminal symbol $A$, that one can derive from it a word $A\alpha$, where $\alpha$ is a word over unified ...
1
vote
0answers
51 views

How would I go about proving that the language accepted by a regular expression is subset of the language accepted by a context free grammar?

Recursive cases: Let A, B be arbitrary RegExps and Let C$_{A}$, C$_{B}$ be cfg(A) and cfg(B) where the properties of cfg can be defined as: cfg($\phi$) = the CFG with no productions cfg($\epsilon$) =...
0
votes
1answer
65 views

Proof verification of the language of all palindromes as being context-free

Consider that the language L of all palindromes over $\Sigma = \{0,1\}^*$ is not context-free. The following is my attempt at a proof by contradiction. I am new to proof writing and I am wondering ...
0
votes
0answers
14 views

When does the initial state lead to empty string when converting a DFA to context-free grammar?

I saw several examples of converting DFA to context-free grammar. Sometimes the grammar output includes the production rule such that the initial state $S$ leads to empty string: $S\to\epsilon$, ...
0
votes
0answers
23 views

How to define context-free grammar which includes words without the last letter from another grammar?

Let $G=(V,T,P,S)$ be a context-free grammar without a production rule for $\epsilon$. Define a new context-free grammar $G'$ which produces every word in $L(G)$ such that the word is without its last ...
0
votes
0answers
73 views

build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

I think it's similiar to NFAs. I replace the finite states of the given automaton for start-states for my new automaton. I do it with $\epsilon$-transition from the start state to the actual finite ...
3
votes
0answers
111 views

Searching for a proof for a variant of the pumping lemma for context free languages

So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the ...
1
vote
1answer
54 views

Show that the following language is context-free/not context free by expressing the language as the union of three other languages.

I want to show that the language $L = $ {$a^mba^nba^p:m=n $ or $n = p$ or $m = p$} is either context-free or not context free by expressing the language as a union of three other languages $L_1$, $L_2$...
0
votes
1answer
98 views

Show that $L=\{a^nb^m : m \neq n\}$ is context free language using closure under union.

I'm trying to solve the following problem. I am asked to show that $L = \{a^nb^m : m \neq n\}$ is context free by expressing this language $L$ as the union of two other context-free languages. ...
1
vote
1answer
42 views

Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$ Generate a cfg of $L_n$

Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$ Generate a cfg of $L_n$ For n = 1, 2, 3 Informally, x is in $L_n$ means some palindrome of at least length n is a ...
1
vote
0answers
31 views

Context Free grammar to Chomsky Normal Form

So I got: $ S \rightarrow XY|a $ $ X \rightarrow XYb|XS|\varepsilon$ $ Y \rightarrow SY|cX|XX|a$ So I want to solve this step by step ( first seperate, avoid length $\geq$ 2, avoid $\varepsilon$, ...
2
votes
1answer
116 views

$L_4 = \{x: \#_{1}(x) = 2 \cdot \#_{10}(x) \}$ Find CFG given hints

Attempt: $S \to A_{00}SA_{11}$ $A_{00} \to 0, 0A_{00}, 0A_{10}$ $A_{01} \to A_{00}1, A_{00}A_{11}, A_{01}1, A_{00}1$ $A_{10} \to 1A_{10}, A_{10}0, 1A_{00}$ $A_{11} \to 1, 1A_{11}, 1A_{01}$ Not ...
0
votes
1answer
36 views

Pumping Lemma for CFL

So I solved some exercises where I have to use the pumping lemma for contextfree languages but this one is a problem for me: Consider: $ L = $ { $w_1£w_2£w_3 \in$ { $0,1,£$}$^*$ | $w_1, w_2, w_3 \...
0
votes
1answer
37 views

Ambiguous CFG to Unambiguous CFG Transformation

I'm having a hard time converting this ambiguous CFG into an unambiguous one. $S \rightarrow Sb \; \mid\; aaSb \;\mid \; b$ If I understood correctly, the language this CFG generates is composed of ...
1
vote
0answers
29 views

Context free grammar with or conditionals

I'm trying to find a CFG for the language: $$L = \{a^nb^mc^o: n = m \text{ or } m \neq o\}$$ The or is tripping me up in the language. So far I have something ...
0
votes
2answers
104 views

Use Pumping Lemma to show that $L_7$ is not context-free

I was studying an old test and struggled to answer this question: Let $L_7$ be the language $\{ w@y \mid y \text{ is a substring of } w\}$, where $w, y \in \{c,d\}^*$. Use the Pumping Lemma for ...
0
votes
1answer
98 views

Show that $\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language by using pumping lemma

$\{a^i b^j c^k \mid i>j>k>0\}$ is not a context free language. I attempted to try this, but I keep on getting stuck. I was planning on solving it like a pumping lemma question for grammar, ...
0
votes
0answers
36 views

Is the language for the following grammar is correct? $L= \{a^i b^j c^k d^l : i,j,k,l \geqslant0 \text{ and }i+k=j+l\}$

I tried to solve it like this: \begin{align} A &\to aAd+S+\epsilon \\ S &\to PQR \\ P &\to aPb+\epsilon \\ Q &\to bQc+\epsilon \\ R &\to cRd+\epsilon \end{align}
1
vote
1answer
47 views

Finding the CFG of a language L

I'm trying to find the CFG of language $$\mathbb{L} = {a^n b^m: n ≥ 0, 2n ≤ m ≤ 3n}$$ I'm completely stuck. I have no idea where to start. Sorry about the formatting on $\frac n m$. Any advice ...
1
vote
2answers
61 views

Prove that the following context-free grammar does not generate the language by finding a word of the language that is not generated by the grammar.

Here is the language: $\{w \in $ {$0,1$}$^* \mid w$ has 2 to 3 times more $0$ than $1$, inclusively$\}$ The following grammar does not generate such language. Prove it by finding a word of the ...