# Questions tagged [context-free]

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

211 questions
Filter by
Sorted by
Tagged with
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-...
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?
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 ...
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: ...
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 ...
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 ...
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:...
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}$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?