# Questions tagged [context-free]

Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

1,189 questions
Filter by
Sorted by
Tagged with
33 views

129 views

### Prove the grammar S → S + S | S / S | 10 | 11 | … | 19 is ambiguous

How to prove the following grammar is ambiguous? S → S + S | S / S | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
72 views

### Context-free Grammar Exercise

Could someone explain me how to form a context-free grammar with all rules R by this example language, please? \begin{equation} L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\} \end{...
69 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: ...
25 views

### Creating a parse tree from two productions

How can I create a parse tree from the two productions below \begin{align} S &\rightarrow 0S2\mid 0T\\ T &\rightarrow 1T\mid\epsilon \end{align} ... to show how 0012 has been made?
28 views

### Is ASM a regular language?

I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world ...
34 views

### Context-free or not: $a^nww^Ra^n$

Is the following a context-free language? $$L = \{a^n w w^R a^n \mid n \geq 0, w \in \{a,b\}^*\}$$ I think no because the number of $w$'s is not equal. Somebody please guide me.
37 views

154 views

### Example of non-regular context free language L such that prefix(L) is regular

Suppose we have some non-regular context free language L. Suppose we also have language of all prefixes of words in L. What can be an example of non-regular language L such that language of it's ...
51 views

### Prove that grammar $S \to aSc | \epsilon | bBc$ ,$B \to bBc | \epsilon$ generates language $\{a^ib^jc^{i+j} | i,j \ge 0 \}$

Prove that grammar $G$ with productions: $S \to aSc|\epsilon | bBc$ $B\to bBc | \epsilon$ Generates language $L = \{a^ib^jc^{(i+j)}$ | $i,j \ge 0 \}$ Step 1. Prove $L(G) \subseteq L$ . ...
19 views

In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim. Consider the grammar: \begin{align*} &R \to XRX \mid S \\ &S \to aTb \mid bTa \\ &T \... 1answer 41 views ### Does every regular language have a linear grammar? Some definitions and facts (from Wikipedia): A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions. the left-linear or left ... 0answers 18 views ### Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete. 0answers 18 views ### Finding a Context- free grammar (CFG) for the language [duplicate] I am trying to find a CFG for the language A below. I have spent hours on this but still could not find the answer. I also came up with the idea that this may not a context- free language but there is ... 1answer 254 views ### Are these special (one production) Context-Free Grammars always unambiguous? Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): S \rightarrow aSb\;|\;\epsilon S \rightarrow aSbS\;|\;\epsilon S \rightarrow ... 0answers 21 views ### Using DPDA instead of LR parsers If LR parsers handle only DCFLs than why we don't just use dpda to parse these languages? What are advantages of using LR parsers over DPDA? Is it that it is easy to built autonomously or something ... 1answer 39 views ### Does this argument prove CFLs are not closed under union? Context free languages are not closed under complementation. This follows from their property of non-closure under intersection: If CFLs were closed under complementation, then they must have also ... 1answer 71 views ### Context-free grammar for \{a^x b^y : x \neq y\} I am trying to create a context free grammar in Extended Backus–Naur form, which starts with a non-empty sequence of a's and is followed by a non-empty sequence of <... 0answers 40 views ### Pushdown Automata for number of a less than 2 times number of b Suppose we want to design a pushdown automata for L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}, can anyone check whether my automata works? we have 4 states \{q_0,q_1,q_2,q_3 \}, three stack symbols ... 1answer 84 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\;|\;\... 1answer 102 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 ... 2answers 69 views ### Proving the decidability of whether a CFG generates a particular string or not Let G be a context-free grammar and w be a string of length |w| = n. Consider the language A_{CFG} = { <G, w> | G is CFG that generates w }, where <G, w> is a string ... 1answer 52 views ### Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form The grammar have the following producitons, \begin{align} S&\rightarrow aTbS \mid\epsilon\\ T&\rightarrow aTb\mid\epsilon \end{align} Already turned this homework in, but I need to convert ... 1answer 29 views ### How to determine valid handle for given bottom up parser? I came across following question: Consider the grammar: E → E + n\text{ | }E × n\text{ | }n For a sentence n + n × n, the handles in the right-sentential form of the reduction are (... 0answers 39 views ### How to find a context-free grammar from a difficult language? [duplicate] Some Languages are trivial to find their respective context-free grammar. Like for example  L= \{a^nb^n: n \geqslant 0\}. However some are really difficult to solve. I would like to have some advice ... 1answer 29 views ### L=\{a^ib^i|i\geq0\}, cfg for L^2 L=\{a^ib^i|i\geq0\}, cfg for L^2 can you write cfg for L^2 where L=\{a^ib^i|i\geq0\}? the professor's answer sheet says it's S\to AA\\ A\to aAb|\lambda but I think it is wrong because two ... 1answer 52 views ### Context-free grammar how to have same number of variables within a language I am trying to get a CFG for the language: The set A of odd-length strings in \{a,b\}^* whose first, middle and last symbols are all the same. (some example of correct answers would be: a, aaa,... 1answer 49 views ### Context-free grammar how to have unequal number of a's on either side of b I have been trying to create a CFG for the set \{w=a^iba^j \mid i \neq j\}. To my understanding, there are essentially 2 scenarios, one where there are more as on the left side of b, and one ... 1answer 26 views ### How to split a context-free language into three sub-languages? I try to split the language L = \{a^ib^j \mid i \neq 2j, i \neq 3j\} into three languages \begin{align} L_1 &= \{a^ib^j \mid i < 2j\} \\ L_2 &= \{a^ib^j \mid 2j < i < 3j\} \\ ... 0answers 37 views ### How to prove that L(G) is not regular by contradicting the pumping lemma? I am trying to prove that this language is not regular by contradicting the pumping lemma. I have been reading and looking at examples but all the examples I have seen is in the for of a REGEX. I am ... 1answer 37 views ### I want to design a context free grammar for the following [closed] This below languageL = \{ w \in \{a, b\}^n : \lvert w\rvert \text{ mod } 3 = 0 \}$$where n \geq0. 1answer 38 views ### How to show that A is not regular? Let Σ = {0, 1, ⊕, =} and define a language A as follows: A = {x = y ⊕ z | x, y, z are binary integers, and x is the XOR of y and z}. For example string “1011 = 1111 ⊕ 0100” is in A, whereas string “... 0answers 30 views ### Conversion of left-recursive context-free grammars to strongly equivalent ones without left-recursion It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-... 0answers 57 views ### Is Python's Grammar in a known Category between CFG and CSG? I have a high level understanding of formal languages and grammars, and I'm familiar with the four major types of grammars in Chomsky hierarchy. I was interested in knowing the classification of ... 1answer 23 views ### Examples of Regular, Context-free and Context-sensitive languages Assume the languages:$$ a) \, L_1 = \{ w \in \{b,c \}^* | \, w \, \text{contains 'bbc' as substring} \}  b)\, L_2 = \{ 1^k 0^m 1^m | k,m \in \mathbb{N} \}  c)\,L_3 = \{ w \in {0,1}^* | \,...
Grammar is as follow: $S \rightarrow aaAb | aab | A$ $A \rightarrow aaAb | aAb | \epsilon$ I think that this grammar has equivalent unambiguous grammar as follow. Let’s first rewrite the grammar ...