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
1answer
384 views

Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither

$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ Exercises: If the language L is regular (build a DFA or regular expression) else if the language L is context-...
-3
votes
2answers
176 views

Grammar for a language with 1/3 of a's

I have this language: $$ L = \left\{ w \in \{a,b,c\}^* \;\big|\; |w| / |w|_a = 3 \right\} $$ where $|w|_a$ is the number of occurrences of $a$. How can I find a grammar that generates it?
12
votes
3answers
19k views

What is complement of Context-free languages?

I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
9
votes
1answer
1k views

Arithmetic expressions grammar transformation

In the article Parsing Expressions by Recursive Descent by Theodore Norvell (1999) the author starts with the following grammar for arithmetic expressions: ...
8
votes
1answer
1k views

Techniques to prove a language is not DCFL

I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL. Are there any other techniques that will help me to ...
6
votes
1answer
412 views

Determining whether a CFG is $LL(k)$ for any $k$?

In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable. Is there a similar result ...
5
votes
1answer
740 views

Deterministic context-free languages are closed under regular right-product

I am looking for a proof for the following problem: For languages $L$ and $R$, if $L$ is deterministic context-free and $R$ is regular, then $LR$ is a deterministic context-free language. Note:...
4
votes
1answer
737 views

Are LR(k) languages and DCFLs equivalent?

In the familiar book of Theory of Computation by M. Sipser, the author proved that for endmarked context-free languages, the set of languages having a LR(k) grammar for a predefined $k \in \mathbb{N}$ ...
3
votes
1answer
2k views

PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

I know the grammar for the language $\{ xy : |x| = |y|, x ≠ y \}$ if $\Sigma=\{a,b\}$: $$ \begin{align*} &S→AB∣BA \\ &A→a∣aAa∣aAb∣bAa∣bAb \\ &B→b∣aBa∣aBb∣bBa∣bBb \end{align*} $$ I ...
3
votes
1answer
843 views

Solving the emptiness problem for a CFG in Chomsky normal form (linear)

Given a CFG in Chomsky normal form, is there an algorithm that solves the emptiness problem in linear runtime? I thought about using depth search here, but I think it's a little bit above linear ...
3
votes
1answer
321 views

Is this a Context Free Language?

I got this question on my final exam: Is the following language context-free? $$ L = \{w\bar w^R \mid w\in \{0,1\}^* \}$$ Notation: The string $\bar w$ is obtained from $w$ by replacing all 0s ...
3
votes
1answer
948 views

Is Myhill-Nerode equivalence class of a language which contains all palindrome pairwise distinct?

In my formal language class, we define a language called PAL, which is on a alphabet set $\Sigma = \{0,1\}$. $PAL = \{w \in \{0,1\}^* : w = w^R\}$. We have proved that every string in this language ...
2
votes
2answers
615 views

What are the modern alternatives to Backus–Naur form and what are their advantages?

I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of ...
2
votes
0answers
75 views

Why CFG can specify structure of sentence but Regular grammar cannot? [duplicate]

CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?
2
votes
1answer
166 views

Can there be a context free language that is not recognizable by a PEG?

This is related to this question. Essentially, I want to know whether my reasoning is correct. We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: ...
2
votes
1answer
151 views

Are Context-Free Grammars with only one Production Rule always Unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $\require{cancel} \cancel{S \rightarrow aSSb\;|\;\...
2
votes
1answer
299 views

How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount

I know that CFG for $$ \{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is $$ S\rightarrow ab/abb/aSb/aSbb $$ but I am not able to tweak it in such a way that it is strictly in between m and 2m and not equal to ...
2
votes
1answer
295 views

Proving that L(G) is the language defined by the CFG G

I have a context-free grammar defined by the production S: S → aSbS ∣ bSaS ∣ ε I need to prove that the CFG "G" can be defined as a language L(G) where L(G) = {w ∈ {a, b}∗ ∶ na(w) = nb(w)}. ...
2
votes
0answers
188 views

Constructing a Context Free Grammar for checking non-equality of strings [duplicate]

I have been studying the book Introduction to Computation by Michael Sipser on my own, and I'm stuck on this exercise from the chapter on Pushdown Automato and Context-Free Languages. The exercise is ...
2
votes
0answers
69 views

Correct bracketing check with rotate operation on position i

Given sequence (length $N$) of brackets like $($ and $)$. The task is to implement data structure which supports following operations: Check whether the sequence is correctly bracketed Rotate bracket ...
2
votes
1answer
2k views

Use pumping lemma to show L is not context free

Show that L = $\{0^{2^n}| n\geq 0\}$ is not a context free language. Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| > 0 and $|vxy| \leq p$. So how do I ...
2
votes
0answers
264 views

Context free grammar as minimal solution of a system of equations

It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example: $$\begin{align*} X &=\{{\epsilon}\} \cup Y\\ X ...
2
votes
1answer
1k views

Pumping lemma for linear languages

Let $L$ be a linear language. Then there is a constant $p$ such that for all $w$ in $L$ with $|w| \ge p$, $w$ can be written as $uvxyz$ where (i) $|uvyz| \le p$ (ii) $|vy| > 0$ (iii) $uv^ixy^iz$ is ...
1
vote
1answer
172 views

Unambiguousness and determinism of CFGs for them to be LR

I came across this statement: Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts. I was ...
1
vote
1answer
1k views

For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free

Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my ...
1
vote
1answer
2k views

Why is the language of even-length non-palindromes context-free?

We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$ is a context-free language. Can anyone help me produce a PDA or give me any hint how I can quickly understand why ...
1
vote
1answer
797 views

Intersection between regular language and context-free language [closed]

In general, context-free algorithm are not closed under intersection but the intersection between a regular language and a CF language is known to be context-free. My question is: does exist an ...
1
vote
2answers
4k views

PDA recognising all strings with a $1$ in the second half

My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says: Let $\Sigma = \{0,1\}$ and ...
1
vote
3answers
381 views

Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$

For the purpose of proving that they are not regular, what closure properties can I use to transform the languages $L_a = \{ a^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$ and $L_b = \{ab^{i_1}...
1
vote
1answer
338 views

Reducing context-free languages with polynomial-time reductions

So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$. Can $L \le_p M$ ? Why or why not? How do polynomial time reductions ...
1
vote
1answer
258 views

Binary strings such that the sum of 0's is not equal to twice the sum of 1's

Construct a context-free language for $L=\{w\in \{0,1\}^* \mid n_0(w)\not= 2n_1(w)\}$. Here $n_b(w)$ is the number of $b$'s in $w$. I can construct a CFL in the case $n_0(w)=2n_1(w)$, but I have no ...
1
vote
2answers
385 views

How Intersection of Regular Language and a CFL is a CFL?

CFL is not closed under intersection. That means, if we have L1,L2 of CFL then L1 intersection L2 is not a CFL And we know, all Regular languages are CFL. Then ...
1
vote
2answers
1k views

Proof Idea: How to prove the intersection of regular language and CFL is a CFL?

I know that the intersection of a regular language and a context free language is a context free language. I've seen this fact proven on here and other websites. However, after spending hours reading ...
1
vote
1answer
230 views

Is Half - Palindrome subset of a context-free language context-free?

Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a ...
1
vote
1answer
2k views

PDA of the language where the number of a's are NOT equal to the number of b's

I have this NPDA for language L = {w: num_a(w) == num_b(w)} all loops in q1 ...
1
vote
2answers
2k views

Is intersection of regular language and context free language is “always” context free language

I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align*} L_1 &= ...
1
vote
1answer
53 views

Exclusion in a context-free language?

I am learning automata theory, and I am confused about this exercise: Give context free grammar to create the following language where the input alphabet is $\{a,b\}$ $L = \{w \text{ where }w\text{ ...
1
vote
1answer
69 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 ...
0
votes
1answer
201 views

Context free grammar for {a^mb^n | m ≠ n} [duplicate]

I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$. This is what ...
0
votes
0answers
132 views

Why does $L=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} \notin CFL$ [duplicate]

Im trying to prove that $L=\{w\#s : |w|=|s|, w \neq s\} \notin CFL$ using the pumping lemma. So I said, let say $L \in CFL$ so by the pumping exists $p$ which is the pumping length of language $L$, I ...
0
votes
1answer
164 views

Closure of context-free languages under “removal of a regular language from the right”

I have a homework that I can't solve can somebody help me? If $\Sigma$ is an alphabet, $R$ is regular and $L$ is context-free. Is the language $$P = \{\alpha\in\Sigma^*\mid \alpha\beta\in L\text{ for ...
0
votes
2answers
4k views

Can context-free grammar generate $a^{2^n}$? [duplicate]

Context-free grammar can generate the string a 2 n for n≥0 . The production rule P is S→SS|a . The derivations is, for example: 1) S⇒a (this is when n = 0) 2) S⇒SS⇒aa (this is when n = 1) 3) ...
0
votes
1answer
60 views

DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$

$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$ Any idea? I have problem with this kind of task.
0
votes
2answers
639 views

CFG for the language L ={a^n w | w \in {b,c}^*, n= count of b.c in w. }

$L =\{a^nw \mid w \in \{b,c\}^*$, $n=$ #$_b$ + #$_c$$\}$ $\bullet $ #$_b$ denotes the number of $b$'s in $w$ $\bullet $ #$_c$ denotes the number of $c$'s in $w$ I have some trouble designing a CFG ...
0
votes
1answer
2k views

Multiple-Choice Questions about decidability

I'm working on old MC-Questions about decidability und don't have the answers to the following ones: 1.) $L_1$ and $L_2$ are not decidable $\Rightarrow$ No superset of $L_1 \cup L_2$ is decidable 2.)...
0
votes
2answers
75 views

if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
0
votes
1answer
789 views

It has been asked to prove that a grammar is unambiguous which seem ambiguous to me

S->aAB A->bBb B->A|epsilon It seems that the string abbbb can be derived by using more than one ways. After using the starting production and the ...
0
votes
2answers
1k views

Finding Language of a CFG

Say you are given the following CFG $G$: $$ S \to S_1 \mid S_2 \\ S_1 \to AbAS_1c \mid \epsilon \\ S_2 \to BaBS_2c \mid \epsilon \\ A \to Aa \mid \epsilon \\ B \to Bb \mid \epsilon $$ What is $L(G)$? ...
0
votes
1answer
1k views

Showing Context Free Grammars that are regular if and only if L(G) = Σ∗.

Suppose that G is a context-free grammar. How can I show that “Is L(G) regular?” is undecidable. Also, prove that L is always context-free but is regular if and only if L(G) = Σ∗. This is what I ...
0
votes
1answer
2k views

Is my proof for a context free language correct? Same number of a's as b's

I have the following grammar G: $$ \begin{align*} &S \to aB|bA \\ &A \to a|aS|bAA \\ &B \to b|bS|aBB \end{align*} $$ I am going to prove that this language L(G) consists of words with the ...