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
33 views

Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$ I've tried the following: $G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \...
-1
votes
0answers
10 views

How to tell if a language is regular or context free based on its description [duplicate]

I dont understand how to tell if a language is regular or context free by just looking at its description. For example question 1.2: how is it not regular? can't we create a regular expression for ...
0
votes
1answer
27 views

What is the relation between a programming language and the language of its input?

I find some references say that all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything ...
1
vote
1answer
20 views

Creating a Deterministic Push-Down Automaton for the Union of two languages

Suppose, we have $L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$. Now we want to create a Deterministic Push-Down Automaton for ...
0
votes
0answers
27 views

Deciding whether CFG generates the empty word

Give an algorithm to decide the following problem: given a CFG $G$, does $G\Rightarrow^\star \epsilon$? That is, given a grammar can it generate the empty word? How can I make sure my algorithm is ...
0
votes
0answers
19 views

Unsure on Proving a Certain Language is Deterministic Context Free

My instructor is stating this is a DCFL. Language in Question: $\{x\in \{0,1\}^* :$ the number of 1's in string $x$ is $>$ the number of 0's $\}$ I can build a CFG to prove this language is ...
0
votes
0answers
26 views

Prove that any PDA/CF language with 1 character is regular [duplicate]

I know there is a post like this already posted, but I didn't quite understand the proof. Can someone explain it to me? Thanks in advance.
0
votes
0answers
13 views

Regular Expression for a^nb^m such that n<= m+3 [duplicate]

I want to know if its possible to write a regular expression for a context free language: For example I have a language : L={a^n b ^m: n<= m +3} I have written the following regular expression ...
2
votes
1answer
120 views

How to simplify context free grammars?

How to simplify this context-free grammar? $$ S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b $$ Can the simplification result in this CFG? $$ S \...
-1
votes
0answers
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
2
votes
1answer
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{...
2
votes
1answer
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: ...
-1
votes
0answers
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?
1
vote
0answers
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 ...
1
vote
0answers
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.
1
vote
2answers
37 views

Difference between $a^{2n} b^n$ and $n_a(w) = 2n_b(w)$

I have encountered two questions related to npda: Construct an npda for $L_1 = \{a^{2n} b^n \mid n \geq 0\}$ as a language over $\Sigma = \{a,b,c\}$. Construct an npda for $L_2 = \{w \in \{a, b, c\}^*...
0
votes
1answer
46 views

Formal languages: What is $2n_c$?

I have got following question: Determine whether the following language is context free or not: $$L = \{ w \in \{a,b,c\}^*: n_a (w) = n_b (w) = 2n_c (w)\}. $$ What is the meaning of $2n_c$ in the ...
0
votes
0answers
11 views

can a PDA without lamda-transition accept every context free language? [duplicate]

I want to know if every context-free-language can be constructed with a PDA without lambda transitions. I have tried to give a counter example but couldn't. Is there a theorem proving such statement ...
0
votes
0answers
21 views

Converting an NPDA to a CFG

I have a question regarding conversion of NPDA to CFG. The above picture is from my lecture slides. I dont understand why they are saying 1 can be popped while transitioning from q0 to q1. It is in ...
1
vote
1answer
35 views

Making a CFG for a^i b^j c^k such that i+k < 3j

I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG. I have thought about solving this for a long time but but this still hasn't gotten me ...
4
votes
1answer
314 views

How to determine if a language is deterministic context-free language?

I have the following question to solve : DCFL means Deterministic Context-Free Language. Let $L$ be a DCFL over an alphabet $\Sigma$. For each of the following functions of $L$, determine whether $...
2
votes
1answer
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 ...
1
vote
0answers
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$ . ...
1
vote
1answer
19 views

Variable derives itself

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 \...
0
votes
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 ...
0
votes
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.
0
votes
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 ...
6
votes
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 ...
0
votes
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 ...
2
votes
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 ...
2
votes
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 <...
0
votes
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 ...
2
votes
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\;|\;\...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 (...
0
votes
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 ...
2
votes
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 ...
1
vote
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,...
1
vote
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 $a$s on the left side of $b$, and one ...
3
votes
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\} \\ ...
0
votes
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 ...
1
vote
1answer
37 views

I want to design a context free grammar for the following [closed]

This below language $$L = \{ w \in \{a, b\}^n : \lvert w\rvert \text{ mod } 3 = 0 \}$$ where $n \geq0$.
1
vote
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 “...
0
votes
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-...
0
votes
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 ...
0
votes
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}^* | \,...
1
vote
1answer
37 views

Is following grammar has language which is inherently ambiguous?

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 ...
1
vote
2answers
44 views

Doubt regarding Chomsky Hierarchy, CFG and CSG

I was following a discussion on a website, where a fellow scholar claims that this grammar S→ aAa | bAb | ϵ A→aA | bA |ϵ is not CSG, so it should also NOT be a CFG. But this grammar properly ...