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

Algorithmic problem of regular, context-free, and recursively enumerable languages

Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free. Are the following problems algorithmically decidable? Is $L_1 \cap L_2 = L_3$? Is $L_1 \...
0
votes
1answer
84 views

Set difference of recursively enumerable language and regular language

Consider a recursively enumerable language L1, and a regular language L2. Is L1\L2 regular, context-free, or recursively enumerable? Is L2\L1 regular, context-free, or recursively enumerable? My ...
0
votes
1answer
36 views

Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} ) (sorry for the formatting, see screenshot-link for conventional/clear ...
-3
votes
0answers
34 views

Express L(G) in set notation

Consider the G grammar below. S ->aSa|A A ->bAb|B B ->ccB|λ Just want to express L(G) in set notation. Could some give me some ideas?
0
votes
0answers
39 views

The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
0
votes
0answers
33 views

How do I upload movies for free to my website for watching movies and TV shows? [closed]

So, I want to make my own website for watching movies and TV shows but not in English but in my native language. So I was wondering is it legal to just upload videos from the openload server or some ...
0
votes
0answers
22 views

Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

I have question where it asks: Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2? Here's what I've done, but I do reach a contradiction... u=a^r v=a^s x=a^t b^N a^...
0
votes
1answer
50 views

Converting PDA to CFG

I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\...
0
votes
0answers
39 views

GATE CSE 2018, Which of the following languages are context-free?

A] {ambncpdq | m+p = n+q, where m, n, p, q >=0} B] {ambncpdq | m = n and p = q, where m, n, p, q >=0} C] {ambncpdq | m = n = p and p not= q, where m, n, p, q >=0} D] {ambncpdq | mn = p+q, ...
0
votes
1answer
28 views

PDA kleene star construction

I know how to prove that CFL are closed under kleene star operation using CFG. I can't find online or in class notes a proof using PDA. I would appreciate description of the basic idea (not formal).
2
votes
1answer
25 views

Context free languages invariant by “shuffling” right hand side

Given a grammar $G$ for a Context Free language $L$, we can augment it by "shuffling" the right hand side of each production, e.g.: $A \to BCD$ is expanded to $A \to BCD \; | \; BDC \; | \; ...
3
votes
1answer
87 views

If $A$ is context-free then $A^*$ is regular

I am currently studying for my exam and I am having trouble to solve this question: Right or wrong: If $A$ is context-free then $A^*$ is regular. I think it's wrong because if $A$ is context-free it ...
0
votes
1answer
97 views

Removing left factoring from Context-Free Grammar

I know that, removing left factoring is a simple task. And i understand following procedure: $S→aA | aB$ Becomes: $S→aS'$ $S'→A|B$ Yet I'm running into problems with this particular grammar: $S→AD|...
0
votes
1answer
23 views

Is it possible to form a PDA for this language?

$$L=\left \{ a^nb^m|n\leq m\leq 2n \right \}$$ Is this even context free? I am asking because by looking at the condition, for an expression that holds:$n< m<2n$ can be written as : $a^nb^nb^c (...
0
votes
1answer
22 views

How can I combine 2 PDA's into 1

I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$} I know the idea of building each one separately but how do I combine them into 1 PDA? LHS: for every 'a' I push 'A' inside stack and for ...
0
votes
0answers
43 views

Is it necessary for a Push down Automaton (PDA) to have a stack?

I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA: Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?
0
votes
2answers
36 views

Build PDA for a language with unknown input alphabet

$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows: $L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$ In this exersice I am not given any ...
0
votes
1answer
87 views

CFG-Infinite recursion

As you see, the string production process never ends. Can someone explain me if this language is regular or not ? $ S \to Α Β S $ $ A \to S $ $ B \to a B b $
-3
votes
0answers
37 views

Context-free language [duplicate]

$$\begin{align}L_1&= \{a^n b^m c^k\ |\ 0<2n\leq m\leq 3n, k = m, n, k,m\in \mathbb{N}\}\\ L_2&= \{a^n b^m c^k\ |\ 0<2n\leq m\leq 3n\text{ or }0<5n\leq m\leq 7m ,n, k, m\in\mathbb{N}\}\...
1
vote
1answer
35 views

CFG that generates $1^*$ is decidable

I read somewhere that the problem which asks whether or not a $CFG$ $G$ generates $1^*$ is decidable. The proof goes like this: $1^* \cap G$ is context free since it is the intersection of a regular ...
1
vote
1answer
47 views

Help with context free grammar excercise

So, I have an exercise in which I have to write a context free grammar for this language: $$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$ meaning every string with any ...
1
vote
1answer
28 views

Why is the following grammar not LL(1)

Consider the following grammar: S → bAb | bBa A → aS | CB B → b | Bc C → c | cC I have to provide the reasons as to why this grammar is not LL(1). So far ...
1
vote
1answer
39 views

Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $

I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language: $$ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $$ I ...
0
votes
0answers
44 views

How to show that language L is NOT context-free?

True or false: To show that a language L is not context-free, one can alternatively show that the union between L and a known context-free language is not context-free. I know that you can prove ...
1
vote
0answers
47 views

How to interpret this context free language?

$S \to aAA$ $A \to aS \mid bS \mid a$ Trivial thing: starting and ending with a Atleast 3 a's are definitely present (These are very layman observations...but seriously I am unable to figure out what ...
3
votes
0answers
44 views

Are there context free grammars for all restricted Dyck paths?

A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...
1
vote
1answer
20 views

closure of Context free grammer to homomorphism using PDA

I was looking online, on sipser book, and on lecture notes and I can't find a proof to closure of context free languages to homomorphism that using PDA instead of CFG. I'm not looking for a full and ...
0
votes
0answers
25 views

Is the emptiness of intersection of two CFLs decidable? [duplicate]

Consider $L = \{\langle L_1, L_2\rangle\mid L_1, L_2 \in \text{CFL} \text{ and } L_1 \cap L_2 = \emptyset \}$. How to prove that $L \notin R $? $L_1, L_2$ encoded in chomsky-normal-form.
0
votes
1answer
42 views

How to remove null production from context free grammar?

How to remove null production and simply the grammar? $$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$ Can the simplification result in this CFG? $$ S \to a \mid aBa \\ A \to ...
-1
votes
1answer
17 views

How to simplify context free grammar?

How to simplify this context-free grammar into a similar one with no unit productions and no useless symbols? $$ S \to ABA \\ A \to aAA \mid aBC \mid bB \\ B \to A \mid bB \mid Cb \\ C \to CC \mid cC ...
2
votes
3answers
1k views

Prove or Disprove: an infinite intersection of regular languages is a context-free language

Let $L_1, L_2,...$ and $L=\cap_{k=1}^{\infty}L_k$ be languages over $\Sigma ^{*}$. Prove /Disprove: if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, then $L$ is a context-free language. I ...
0
votes
0answers
11 views

Does all derivation trees generated by context free grammar in cnf form can be recognized by buttom up tree automata?

G is a context-free grammar in Chomsky normal form. we define L(G) to the set of all derivation trees that formed by G. Is it possible to create a non-deterministic bottom-up tree automaton that will ...
0
votes
0answers
57 views

What does it take to create a new programming language and its toolchain?

I am super novice to this topic, so my apologies if my question looks completely nonsense to you all! Imagine you want to create a new programing language that transpiles to a more common high/low-...
0
votes
0answers
25 views

Upper bound on size of derivation in CFG

Suppose $G$ is a $CFG$ with $m$ variables, in which the right-hand side of all production rules has length at most $\ell$. Show that if $A\Rightarrow^*_G\varepsilon$, then there is a derivation of no ...
1
vote
1answer
378 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 ...
1
vote
1answer
197 views

What are the known ambiguities in C language grammar?

I have found this reference for the C syntax Backus-Naur Form (BNF). I was wondering if there are any other ambiguities in this grammar other than the infamous "dangling else"? Also how we ...
0
votes
1answer
16 views

Predicitve Parser LL(1) condition

Lets say we use the predictive parser LL(1). Why is it necessary that $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$, for all $\alpha, \beta$ right side of alternative productions i.e., productions ...
0
votes
0answers
14 views

Convert PDA by final state in to cfg

Hope you all are doing well. I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask, If I want to first convert this into ...
2
votes
1answer
31 views

Language of lists of words, not all of which are different, is not context-free

How do I prove that the following language isn't context-free using the pumping lemma? $$ L=\{w_1\#w_2\#\dots\#w_k \colon k ≥ 2, w_i \in \{0,1\}^*, w_i = w_j \text{ for some } i \ne j\} $$ I am having ...
0
votes
0answers
23 views

Context free grammar to Chomsky normal form

I have a hard time understanding how to convert the following context free grammar to Chomsky Normal Form: S $\rightarrow$ aSX | B B $\rightarrow$ bBX | ε X $\rightarrow$ a | b I have a solution S $\...
2
votes
1answer
33 views

Is s-grammar powerful enough to generate all possible DCFL?

In s-grammar all productions are in form of A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V* "... and any pair (A, a) occurs at most once in P." [P. Linz, 6th ed. , p. 144] s-...
14
votes
1answer
450 views

Is the language of words that are unbalanced in the first half context-free?

(Practice exam question in computational models) Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s. Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
0
votes
0answers
29 views

How to determine if a language produced by grammar is recognizable by deterministic pushdown automaton (DPDA)? [duplicate]

I have a following grammar: S -> aSa | bSb | $\lambda$. And I have to figure out whether the language produced by this grammar is recognizable by DPDA. I can't find any theorems about it. Obviously, ...
0
votes
1answer
26 views

Is there any property about height of PDA?

I'm trying to find a PDA for $L$ which modifies the stack height at most one. $L=\{a^ib^i\mid i\geq 0\}$ I think there is no such PDA but how can I prove it? My attempt is for a given string, find ...
0
votes
0answers
16 views

Redcue CFG-Eequiv to CFG-SYM [duplicate]

I want to show, that for an CFG G the question wether $L(G)=L(G)^R$ is undecidable. My first try was to reduce from the CFG-Equivalent Problem) $CFG_{EQUIV}\leq CFG_{SYM}$. My first attempt was to ...
0
votes
0answers
29 views

Is language bin(n)bin(2^(k+1) n + 1)^R context-free

I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R \},$$ where $\cdot^R$ reverses a string and $\...
1
vote
1answer
86 views

Is every linear language in NL?

I wonder if all the linear languages are in NL? I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the ...
0
votes
2answers
26 views

Is the language of rectangular matrices in MATLAB-style syntax context free?

Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be ...
0
votes
0answers
55 views

context-free language : if yx belongs to cfl then xy is also cfl [duplicate]

I faced a problem. What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language. C is a Context-Free Language. I think we can use the PDA ...
0
votes
1answer
32 views

Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }. This is really confusing me, I'm having trouble with ...

1
2 3 4 5
27