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
1
vote
1answer
50 views

Can you reduce every decidable language to a regular language?

One of my previous questions on an exam was the following Can you reduce a decidable language to a given regular language? (decidable language $\leq _m$ regular language). If so, does this mean that ...
2
votes
4answers
54 views

If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular So far I know that: There are examples where $L$ ...
1
vote
2answers
967 views

Are all finite languages context-free?

As far as I know, finite languages have a finite number of strings or words, while context-free languages are generated by context-free grammars. I don't know which aspect should I know that they are ...
1
vote
2answers
44 views

Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

I have found an exercise where it tasks to provide a grammar and a pushdown automata for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$ While finding a pushdown automata for it is quite easy (four states and two ...
1
vote
3answers
52 views

Regular Expression for language [duplicate]

I have a grammer with the following productions, S -> aA | bC | b A -> aS | bB B -> aC | bA | a C -> aB | bS I have to construct regular expression for ...
1
vote
2answers
184 views

Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')

I am trying to remove ϵ rules from the following grammar (after applying the remove redundant symbols algorithm): $G = (\{S,A,B,C\},\{0,1\},P,S)$, where the productions are \begin{align} &S \to AB ...
1
vote
1answer
49 views

Number of sentences and sentential forms generated by a grammar

In this question, I'm considering only "finite grammars". A finite grammar can only produce a finite number of distinct sentences. The following grammar is finite in my definition: ...
2
votes
1answer
66 views

Which closure properties are always valid between regular, context-free and non context-free languages?

I am making a scheme that respresents some closure properties (union, intersection, complement and concatenation) for regular languages, context-free languages, decidable languages and RE languages. ...
4
votes
1answer
43 views

Is there a method to generate the complement of a context-free grammar?

Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find ...
0
votes
1answer
21 views

Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?

How is it possible to prove whether the language $\{a, b\}^{∗} \setminus \{S → ε, S → aSbS\}$ is context free?
4
votes
1answer
220 views

Context-free grammar for all words not of the form w#w

I was asked to define a CFG for the complement of $\{w\#w \mid w \in \{0,1\}^*\}$ and I'm struggling to define it. I think it is quite similar to defining a CFG for the complement of $\{ww \mid w \in \...
2
votes
1answer
60 views

Context Free Grammar to Regular Expression?

I want to learn whether I can create regular expressions from the given Context Free Grammar. I found some examples that can be translated to regular expressions. However, all of them were like this: &...
1
vote
1answer
49 views

Is there a pushdown automaton for $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$?

According to this statement: Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular ...
0
votes
1answer
33 views

If L is context free and R is regular then R – L must be context free?

Hi I am wondering if L is a CFL and R is RL then would the difference R - L be a context free language? The difference might be the CF part of the language left then it would be, but I'm not sure how ...
1
vote
1answer
34 views

Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$

I would like some help for the computation theory. There is a PDA that accepts the language $\{0^n 1^a 2^b \mid n = a+b\}$, so how can I express it into context free grammar? Any help would be ...
1
vote
1answer
30 views

Trying to find two CFGs for the following languages

I'm trying to get CFGs for these two languages which still remain unsolved in my practice problems sheet: $L = \{ a^kb^ra^m | m=k+r\}$ $L = \{ a^nb^m | 1\leq n\leq 2m\}$ With the first one, I thought ...
0
votes
1answer
61 views

Drawing a DPDA for the language $L=\{w\in\{a,b\}^*|n_a(w)=n_b(w)\}$ in Sipser's format

As I know $L=\{w\in\{a,b\}^*\mid n_a(w)=n_b(w)\}$ is a deterministic context free language. I have drawn a push dawn automata for this language in the format of Sipser as the following However, as ...
2
votes
0answers
22 views

closure property violated by palindrome language

It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The ...
0
votes
0answers
22 views

Need some guidance on CFG pumping lemma proof

I'm currently stuck on a homework problem, and I feel completely lost about how to solve it. Generally I find pumping lemma proofs to be pretty straight-forward, but I feel like I'm missing something ...
0
votes
2answers
64 views

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? If so, can there be a pushdown automaton described for it? If not, does the pumping lemma apply?
2
votes
1answer
45 views

Construct a CFG for $L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$

I need to construct a CFG for the following language$$L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$$ I know that the two middle position should always be the ...
1
vote
1answer
34 views

CFG to CFL conversion (production rule with both left and right recursion)

Is there a general rule to convert a CFG to its CFL? For example, how do I approach the following question? What is the language generated by the following CFG? $$ S \to aS \mid Sb \mid \epsilon $$ ...
0
votes
1answer
23 views

Can PDA accept only by final state without finish reading input?

I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
0
votes
2answers
64 views

Determine if the language of words with same number of 1's and 2's is context-free or not

$$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$ I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 ...
0
votes
0answers
24 views

Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1| A -> 0A|1A|𝜖 How can i interpret the odd number of 1's also?
0
votes
1answer
34 views

Can someone please help with the proof of this?

Given an unambiguous context-free language L and an unambiguous regular language L (moreover, every regular language is unambiguous) such that L∩ R = ∅, then prove that L∪ R is also unambiguous.
0
votes
1answer
19 views

Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$

Given the following language, I am tasked with giving a context-free grammar that generates it. $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$ Would this be correct? $A \rightarrow aaaA$ $B\...
3
votes
1answer
88 views

Deciding whether complement of context-free language is context-free

I need to find out if the following problem is decidable: Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language. I am having trouble in defining ...
0
votes
1answer
59 views

I'm trying to prove this language is not context-free: {a^x b^y c^z | where x=z and x<y}

So far i've tried with making x = z = p and y = 2*p, but it seems that if I place vxy to represent all b's then I can't get a contradiction.
0
votes
0answers
6 views

Generating context-free grammar from a language [duplicate]

Consider this language $L=\{a^n b^m c^k | k \neq n+m\}$ Can somebody tell what is the context-free grammar of L?
1
vote
1answer
43 views

Is this language based on the number of $a$'s of a word over alphabet ${a, b}$ context-free?

I'm trying to use the pumping lemma, to show that the language $L = {w \in \{a, b\}^+: na(w) = nb(w)}$ is not context free, where $na(w)$ is the number of $a$'s in $w$. I have this: By contradiction, ...
3
votes
1answer
105 views

Why do we need two variables for implementing kleene star operation on a language using context free grammars?

I have a Context-Free Grammar (CFG) G which has a S for generating a language L. Now to produce a grammar for L*, another variable T (which is not present in the variable set of G) is taken and the ...
0
votes
1answer
67 views

{a^n b^n c^n | n>=1} - PDA

I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive. How I attempted it ...
1
vote
1answer
19 views

is the intersection of a context free language and a regular language a two way street?

I wasn't sure how to word it correctly, hence the 'two way street' in the title. My question is: The intersection of a context-free language and a regular language always results in a context free ...
0
votes
1answer
33 views

Formal proof of language accepted by a specific CFG

Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules: \begin{align} &S \to aS \mid B \\ &B \to abBc \mid \epsilon \end{align} Please provide a formal proof for the following ...
0
votes
1answer
84 views

Decidability of PDA

I have following problem: INFPDA={⟨A⟩ |A is PDA and L(A)=infinite language} Prove that this is decidable problem. So my idea how to solve this problem is the ...
0
votes
1answer
40 views

What to do following a reduce in LR(1) parsing?

I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C->d, now what ...
0
votes
0answers
14 views

Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
1
vote
1answer
34 views

How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?

This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\...
0
votes
0answers
36 views

Context-Free Grammar Question

Given a regular Expression: 0^a 1^b 0^c, where a+b=c and a,b,c >= 0. Find the cfg for this expression. Here is what I tried to do: s -> AsB A -> 01 B -> 0 But then a language could be ...
0
votes
1answer
32 views

Is this an unambiguous CFG that is not LR(k) for any k?

The grammar is this: $$S \rightarrow a B c $$ $$B \rightarrow b B b $$ $$B \rightarrow \epsilon $$ The LR(1) states that I worked out were these $$(1)$$ $$S \rightarrow .aBc$$ $\\\\$ $$(2)$$ $$S \...
1
vote
0answers
19 views

CFG for the language x^n y^m, where n ≥ 1, m ≥ 1, and n ≠ m [duplicate]

Can anyone help me construct a CFG for this? It really has me stuck for some reason.
3
votes
0answers
87 views

is it decidable whether a grammar in Chomsky normal form has useless rules?

Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
4
votes
1answer
307 views

Undecidability of “is this CFG prefix-free?”

I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition). Another thread has the very different question "...
0
votes
0answers
20 views

Constructing a Push Down Automaton

Given a 7 tuple push down automaton M = (K, Σ, Γ, Δ, s, F) where K = {p, q, r}, Σ = {a, b, c}, Γ = {a}, s = p, and F = {r}, with the transitions ((p, b, ε), (q, ε)), ((q, a, e,), (p, a)), ((p, c, a), (...
-1
votes
1answer
39 views

Transform grammar to Chomsky Normal Form

Question: S → abSab | baSba | TT T → aTa| bTb | ε My answer: Eliminate ε rules: S-> abSab | baSba | TT | T T-> aTa | bTb | aa | bb Correct answer: S → abSab | baSba | TT | abab | baba | T T → ...
3
votes
1answer
68 views

A language that is not context free

I working through some textbook exercises, and came across a problem that I'm struggling with. Give a CFL $L$ such that $\{x|\forall y \in \Sigma^* \space xy \in L\}$ is not a CFL. I've got the idea ...
0
votes
0answers
16 views

Constructing a context free grammar with starting state

I'm supposed to construct a context-free grammar generating all strings in : {(ab)$^{m}$c$^{n}$(ba)$^{m}$ : m, n, ≥ 0} So far I have V = {A, S, a, b, c}, Σ = {a, b, c}, and R = (1) S -> A (2) S -&...
1
vote
1answer
53 views

CYK - finding the closest word accepted

Let's say I have a context-free grammar G and a string S. The normal CYK algorithm outputs that s can not be build using G. How would I find the closest String S' that can be build using G?
1
vote
1answer
42 views

How to find the language of a CFG from Production rules

I'm having problems in finding language of the CFG from given production rules. For example if the production rules are \begin{align} &S \to AS \mid \epsilon \\ &A \to aa \mid ab \mid ba \mid ...

1
2 3 4 5
28