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

Converting Context Free Grammar to Greibach Normal Form

I'm having a hard time with this example. In order to convert CFG to GNF I follow these steps required by my professor: Convert grammar to Chomsky NF (remove useless symbols (non-generating, then non-...
0
votes
0answers
19 views

Is CFL complement PTIME?

Is CFL complement PTIME? If so, why? Im sure it's NPTime because i can verify is some word is (not) in CFL using CYK algorithm. (In polynomial time) But what about PTIME?
0
votes
2answers
26 views

Is the given Language $L$ regular?

$L = \{ a^nb^m : m + n\text{ is divisible by }3 ; m,n\ge 0\}$. Is this language regular, and if so, what is the regular expression?
0
votes
0answers
14 views

pumping lemma for context free languages

As part of the homework we were asked a question about context free languages, and the proof is done using the pumping lemma for CFL. (Prove that it is not a CFL, proof by negation.) The question is ...
2
votes
1answer
61 views

CFL grammer questions

I'm preparing to my test and I have 2 question in past test with no answers. Could you help me? Prove or disprove the following claim. The language $$L=\{a^n\mid n!=k^2, k\ge 0\}$$ is a CFL. I now ...
3
votes
2answers
81 views

Is this language $L$ context free?

$L$ is a language combined with the symbols $\texttt{a}$, $\texttt{b}$ and $\texttt{c}$ given by: $$ L = \{ v\texttt{c}w \mid v, w \in \{ \texttt{a, b} \}^*\text{ and } v \neq w \}.$$ I tried to prove ...
1
vote
1answer
14 views

Determine if complement of non-regular language is context-free

I'm trying to understand if the complement of non-regular language is context-free. for example: $L=\{ 0^n 1^n │ n\ge0 \}$, I need to prove that the complement of $L$ is regular so $L'$ is context-...
0
votes
1answer
26 views

Is there a context free grammar that is both in Chomsky Normal Form and ambiguous?

I know that converting an ambiguous context free grammar (CFG) to be in Chomsky Normal Form (CNF) might make it unambiguous, but is it a method that necessarily makes any CFG unambiguous? My knowledge ...
0
votes
1answer
21 views

If L* is context-free, is L context-free as well?

I know CFL in closed under Closure, but don't know how to prove it back. I try to construct a CFG for L* such as S->ε|AS and say since L* in a context-free language, there must exist a method to ...
0
votes
2answers
126 views

Pumping Lemma for CF language exercise

I have this language $$ B=\{x\in \{a,b,c\}^*:(x\text{ not contains } aabb \text{ or } bbcc \text{ or } aaaa) \land \#(a,x)=\#(b,x)=\#(c,x)\} $$ The notation $ \#(s,x) $ indicates the number of ...
0
votes
1answer
19 views

Is every sentential form also a right-sentential form?

Ullman's Introduction to Automata, Languages and Computing (1979) says 10.6 LR(0) GRAMMARS ... A right-sentential form is a sentential form that can be derived by a rightmost derivation. Is every ...
0
votes
0answers
11 views

How to characterize the set of grammars which recursive descent parsers can apply to?

How would you characterize the set of grammars which recursive descent parsers can apply to: no left recursion (both immediate and not) left factored no cycle no epsilon rule ... Predicative ...
0
votes
1answer
16 views

Context free grammar for language $\{ \{a,b\}^*$: where the number of $a$'s is unequal to the number of $b$'s$\}$

I've seen many solutions for when the number of $a$'s and $b$'s ARE equal but how should the grammar be for the time when the numbers are unequal? So far I have this but it can't produce many things ...
-1
votes
1answer
44 views

Formally proving that $\{ L = { {a^i}{b^j}{c^k}, j = \min(i,k), i, k > 0\} } $ is context-free

Please no hints. I need to formally prove that $\{ L = { {a^i}{b^j}{c^k}\mid j = \min(i,k),\: i, k > 0\} } $: At first my idea was to use pumping lemma, so I tried to study where $\\|vwx|\ $falls ...
1
vote
1answer
49 views

Prove that $L=\big\{\langle G\rangle \mid G\text{ is a CFG over }\Sigma=\{0,1\}\text{ and }1^* \cap L(G)\ne\varnothing\big\}$ is decidable.

How to prove that $L = \big\{\langle G\rangle \mid G \text { is a CFG over } \Sigma = \{0,1\} \text { and } 1^* \cap L(G) \ne \varnothing\big\}$ is decidable? I know I am supposed to prove that it is ...
0
votes
0answers
15 views

What is the minimum and maximum number of productions in Chomsky and Greibach Normal forms?

How many min and max number of productions will be required in Chomsky Normal Form(CNF) and Greibach Normal From(GNF) each if string length = n ? I've heard somewhere that in GNF, minimum and max ...
0
votes
0answers
19 views

Do CFG' concepts of derivation and derivation tree apply to grammars more general than CFG?

Ullman's Introduction to Automata, Languages and Computation (1979) says that given a CFG $G$, Two strings are related by $\to_G$ exactly when the second is obtained from the first by one application ...
0
votes
0answers
15 views

Chomsky Normal form for any CFG that doesn't generate ⋋?

Can someone explain me this statement? It is easy to find Chomsky Normal form for any Context Free Grammar that doesn't generate ?
0
votes
1answer
14 views

Is every production in a CFG an $A$-production?

In Ullman's Introduction to Automata, Languages and Computation (1979): A context-free grammar (CFG or just grammar) is denoted $G = (V, T, P, S)$, where $V$ and $T$ are finite sets of variables and ...
0
votes
1answer
18 views

What are the gists of CNF and GNF of CFG's?

https://en.wikipedia.org/wiki/Chomsky_normal_form#Chomsky_reduced_form says A formal grammar is in Chomsky reduced form if all of its production rules are of the form: $$ A\rightarrow \,BC$$ or $$A\...
0
votes
0answers
16 views

Are there subset/superset relations between the languages which can be parsed by these different kinds of parsers?

I have been confused by the different types of parsers listed in https://en.wikipedia.org/wiki/Parsing#Types_of_parsers and https://en.wikipedia.org/wiki/Template:Parsers Are there some top-down and ...
1
vote
0answers
26 views

Is a CFL parser counted as an automaton, and even a PDA?

Is a CFL parser counted as an automaton? Even more, is a CFL parser counted as a PDA? I found that a CFL parser is defined directly based on a CFG, while the concepts of CFG and PDA are defined ...
0
votes
1answer
38 views

How to use the pumping lemma to prove that $a^{m}b^{n}a^{m}c^n$ is not context free?

How to use the pumping lemma to prove that $ Y = a^{m}b^{n}a^{m}c^n$ is not context free? Note that $m,n \ge 0$. I tried by finding the case where it would be impossible for a word $w$ to be in $Y$. ...
1
vote
1answer
11 views

How to transform a regular expression into a context free grammar with 2 variables?

I'm tasked with transforming this regular expression $((0+1)(0+1)^*(0+1))^*$ into a context free grammar. As an added constraint I'm must do so with a maximum of 2 variables. This is what I did : <...
0
votes
0answers
10 views

Reachable Grammar Symbols

Consider the grammar $G = {V,T,P,S}$. Consider the inductive algorithm whereby we find the set of reachable symbols for the grammar $G$ Basis: S is surely reachable Induction: Suppose we have ...
0
votes
0answers
14 views

Can each type of formal languages be defined in terms of applying operations in (full) AFLs/trios to some base languages?

The four types of formal languages in Chomsky hierarchy, i.e. regular, CFL, CSL and r.e., are all (full) trios and (full) AFLs. Does that mean that each of the four types of languages can be defined ...
0
votes
1answer
40 views

How to prove that the language L={w1#w2#. . .#wk: k ≥ 2, each wi ∈ {0,1}^* , and wi = wj for some i !=j} is not context free using the pumping lemma?

I am having trouble choosing the string to use for the proof. I know that I have to choose a string such that at least two substrings separated by the # are equal to each other but am unsure of how to ...
0
votes
1answer
20 views

Is A -> BB valid under Chomsky's normal form?

A → BC, or A → a, or S → ε, Above is the typical definition given on Wikipedia and in textbooks. Nothing i can find says the B and C variables have to be ...
0
votes
1answer
20 views

What are the relations between pushdown automata and parsers?

For a CFG, there is a pushdown automaton; vice versa. For a CFG, there is a parser; and I guess vice versa? What are the relations between pushdown automata and parsers? Are they directly related? ...
1
vote
0answers
19 views

for language L={a^n b^m c^l d^k | n==l,m==k} is correct or not?

Is it correct or not? Is this PDA NPDA or DPDA? I'm confused. Someone please answer me. Here I created PDA for the language
0
votes
0answers
7 views

Intersection and union between two context-free languages

It has been difficult for me to demonstrate these two exercises, I hope they can help me. this is the problem I think the union is a free-context language.
0
votes
1answer
23 views

Converting linear grammar to normal form

I have a grammar that has the following productions: $S\to aSbb$, $S\to aSa$ and $S\to c$ I am supposed to convert this grammar to normal form where the productions have to be as follows: $A\to aB$ ...
0
votes
1answer
38 views

Proof for pumping lemma for new kind of CFL

I have a context-free grammar $(V,\Sigma,R,S)$ that is defined by the condition that every production in $R$ has to be on one of the following two forms: $A\to uBv$ where $A,B\in V$ and $u,v\in\Sigma^...
1
vote
1answer
35 views

Convert grammar into Chomsky Normal Form

I am trying to convert grammar into Chomsky Normal Form (CNF) but something is going wrong. I need some help. Can someone explain it, please? Here is grammar: S $\rightarrow$ aSc|X X $\rightarrow$ ...
0
votes
0answers
27 views

When our two-state PDA constructed from CFG is non-deterministic PDA?

We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
0
votes
0answers
34 views

Regular Languages

i am stuck in this problem. Prove that shuffle of 2 Context-free Languages is Recursive and Recursive-enumerable. Also prove that this new language is not necessarily Context-Free. I am able to do the ...
0
votes
0answers
13 views

A Prolog grammar problem

What will be the answer of this? Consider the grammar $G = (V , T , S, P)$ where the start symbol is $S$ with a set of non-terminals $V = \{S,A,B\}$, a set of terminals $T = \{c,f\}$, and set of ...
1
vote
0answers
16 views

$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} ~:~ v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, ~ \text{k even} \} $ is context free language

Let $\mathcal{L}$ be context free language over alphabet $\Sigma$. Define $\mathcal{G}$ as $$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} ~:~ v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, ~ \text{k ...
-1
votes
1answer
32 views

Constructing CFG for even length words with maximum of two 0's

How to I generate a CFG from the language that have even length and have at most two 0’s L3 = {w ∈ {0, 1} ∗ | w is even length, 0<=2 } I feel stuck on meeting the criteria of maximum two 0s My ...
1
vote
1answer
41 views

Finding Context free grammar from a language

I am trying to construct context-free grammar from the following language accepted by this PDA $L(A)=\{a^n c^m b^{2n} \mid n, m \in {\Bbb N}, m \geqslant 2 \}$ I am particularly stuck on how to ...
0
votes
2answers
60 views

CF grammar for a Language.

I am trying to formulate a CF grammar for a language of alphabet { a , b, c} with a condition that the number of characters a standing anywhere in the word before this given c larger by 3 than the ...
0
votes
1answer
19 views

Finding the context free language

I am a self taught software developer and i came to a problem which i can not solve , can you please help me find the context free language of this language? Thank you . Here is the example , i ...
0
votes
2answers
68 views

If a language is Turing decidable, does that make the sublanguages also Turing decidable [duplicate]

Let $L$ be a language over a finite alphabet $A$. A language $L'$ over the same alphabet $A$ is called a sublanguage of $L$ if $L' \subset L$. Assume that $L$ is Turing-decidable. Does it follow that ...
0
votes
1answer
34 views

formal languages write context-free grammar

I have been confusing a question for 2 days. I think I solved the question, but I don't know if it's true. Can you help me tell me I did it right or wrong? The question is ; Write a context-free ...
0
votes
1answer
21 views

How is $\{uv \in \{0,1\}^* | \space|u|=|v| \text{ and } u\neq v \text{ at exactly 2 characters} \}$ not a CFL?

I'm looking at the following language, and it is given to me that it is not a CFL: $$\{uv \in \{0,1\}^* | \space|u|=|v| \text{ and } u\neq v \text{ at exactly 2 characters} \}$$ However, if I ...
0
votes
2answers
140 views

context free grammar that generates binary all numbers divisible by 3

I'm struggling with the grammar that generates all binary numbers divisible by 3 I know that for a binary number to be divisible by 3 the sum of 1s in even bits mines the sum of 1s in odd bits must be ...
0
votes
1answer
34 views

Is the language $𝐿=\{𝑎^𝑖.𝑏^𝑗.𝑐^j.𝑑^i:𝑖,𝑗≥0\}$ context free language? [closed]

Is the language $𝐿=\{𝑎^𝑖.𝑏^𝑗.𝑐^j.𝑑^i:𝑖,𝑗≥0\}$ context free language? If yes, what is the context-free grammar?
0
votes
1answer
23 views

How can I find the CFG for this language?

Any help is appreciated as I am stuck in a difficult course with a truly awful professor. I am trying to get the CFG for this CFL, but it's really throwing me. $$L=\{x\#y^R\mid x,y∈\{0,1\}^*,\ x≠y\}$...
0
votes
1answer
26 views

Context free grammar of $L = \{w \in \{a, b, c\}^* : |w|_{c} = 3k +1 \}$

So, this is my first homework in conext free grammar, I want the grammar that generates all possible words in L, I have come out with the following rules $$ S \rightarrow aS | bS| cX\\ X \rightarrow ...
0
votes
0answers
19 views

Transforming a grammar $G$ to Greibach normal form

$ \newcommand{\rewrite}{\longrightarrow} \newcommand{\lang}{\mathcal L} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\perm}[1]{\left\langle #1 \right\rangle} $ I would like to transform the ...

1
2 3 4 5
17