Questions tagged [context-free]

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

202 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
57 views

Grammar for context free language

I want to give a grammar for the following language: $$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$ where $x ^ r$ denotes the backward written ...
0
votes
0answers
66 views

Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free

I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language. Let $L=\{a^ib^kc^k : i\geq k\geq 1\}$ and the followings are my attempt. Proof. Suppose by ...
0
votes
0answers
174 views

How can I find a language from a given PDA

I have the following PDA: And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{...
0
votes
0answers
50 views

Get grammar from his LALR(1) parsing table

I have a problem with this exercise. This is the LALR(1) parsing table for the grammar G. How can i get the productions of G? Thanks :)
0
votes
0answers
22 views

Are there any formal grammars describing the set of all directed graphs?

Let GRAPHS be the set of all directed graphs. Is there a set of strings STRYNGS such that there exists a bijection ...
0
votes
0answers
41 views

Prove this Context-Free Grammar is Ambiguous

so I have a problem on one of my computational structures final reviews, and I cannot seem to figure it out. It's been driving me crazy, so I would like to post it here for some insight. Prove that ...
0
votes
0answers
163 views

When proof by induction on length string is not possible?

I found out an exercise where you have to prove the correctness of the following CFG: Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and $\: G: S\rightarrow 0S11 | 0S111| \epsilon$ claim: Every string $w ...
0
votes
0answers
37 views

Prove the language L of all palindromes over {0,1} is in NP

Wouldn't this language be in P, since it is a context free language. And every context free language is a member of P? Or would it be otherwise?
0
votes
0answers
103 views

Is $\{ a^i b^j c^k : i + 1000\ < j + 100 < k \}$ context-free?

I have this language: $$ L = \{ a^i b^j c^k : i + 1000\ < j + 100 < k \}, $$ and what I believe is that we can't prove with the Pumping Lemma that it is not context-free, because we would ...
0
votes
0answers
152 views

Are there any context-free languages that are not regular but can be generated using a right-linear or left-linear grammar?

I understand that every regular language can be generated using either a right-linear or left-linear grammar, however, does that go the other direction? In other words, do there exist any context-free ...
0
votes
0answers
39 views

Computing the shortest path in a labyrinth

I'm currently trying to map how to make a good algorithm that won't have issues to find the shortest path. The labyrinth consists of an X and Y dimensions as input; However, the labyrinth will ...
0
votes
0answers
109 views

Polynomial time verifier for $\overline { EQ_{CFG}}$

How to find, or prove impossible, apolynomial time verifier for $\overline { EQ_{CFG}}$? $\overline { EQ_{CFG}}$ means all pairs G and H, which are CFGs such that L(G) is not equal to L(H)
0
votes
0answers
457 views

Deciding whether a context-free grammar's language is empty

Consider the formal problem: Given a context-free grammar $G$, is the language $L(G)$ empty? Can we determine if the problem is recursively enumerable, recursive, in NP, or in P? Can the entire ...
0
votes
0answers
275 views

Proving infinity of CFL with pumping lemma

Given a CFG G in Chomsky Normal Form with n variables. Prove that $|L(G)| = \infty \iff \exists w \in L(G)$ such that $2^n<|w|\le2^{n+1}$ Now, proving left to right I've encountered a problem. ...
0
votes
0answers
186 views

How to show that a language is strictly context sensitive

During a class, we was asked how to prove that a language L is strictly context-sensitive. In particular, we have to prove that $L = \{a^nb^nc^n \mid n > 0\}$ Could you help me to find the ...
0
votes
1answer
531 views

LL1 parsing algorithm for strings generated by a given grammar

How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar? I have to design a parser for a specific grammar. Let $G$ be the grammar described as: $$S \...
0
votes
0answers
24 views

Operation on languages results in CFL

For every two languages $L_{1}$ and $L_{2}$ over the alphabet $\{ a,b,c,d \}$, we define the language $$L_{1} \operatorname{op} L_{2} = \{ \alpha\beta \mid \text{$\alpha \in L_{1}$ and $\beta \in L_{...
0
votes
0answers
49 views

Interpreting the way we choose partitions in the pumping lemma for CFLs

This question is referring to the Pumping Lemma for CFLs, namely: If $L$ is a CFL, there is a pumping length $p$ such that any string $z \in L$ of length $\geq p$ can be written as $z = uxwyz$, ...
0
votes
0answers
95 views

Doubt regarding Chomsky hierarchy

I know that intersection of CFL and regular language is CFL and hence CFL is closed if one of the languages is regular. One of the most common examples to show this is regular language being $p^*q^*$ ...
0
votes
0answers
140 views

Is this grammar in Chomsky Normal Form?

This was the initial CFG (starting symbol is I): I → aAB A → BAb | ε | B B → a | b | CD C → ba D → DD And this its CNF: ...
0
votes
0answers
340 views

CFL Intersection with Regular Language prove

how can i prove the following statement : 1- $L_1\subseteq\Sigma^*$ is CFL and $L_2\subseteq\Sigma^*$ is regular Language, then $L_1$\ $L_2$ is CFL . so i want to know what is the method to prove it ...
0
votes
0answers
55 views

Is this grammar L4 ambiguous?

S-> AAB|ABA|BAA|epsilon A->aS B->bS this is a grammar of the language L4 = {w ∈ Σ*: #a(w) = 2#b(w)} over Σ = {a, b} Does the following examples shows that the L4 is ambiguous? S->AAB->aSAB->aAB-...
0
votes
0answers
960 views

Can any left recursive grammar be converted into equivalent right recursive grammar and vice versa

I know how to convert any Left Linear Grammar (LLG) to Right Linear Grammar (RLG) and vice versa. This can be done as follows: Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB ...
0
votes
2answers
3k views

Removing epsilon transition from context-free grammar

I have the following context-free grammar from which I have to remove epsilon transitions: $S \to 0A0|0$ $A \to BC|2| CCC$ $B \to 1C | 3D | \epsilon$ $C \to AA3 | \epsilon$ $D \to AAB | 2$ By ...
0
votes
0answers
70 views

How can I build this automaton?

The automaton has to recognize the language $(a^n)(b^m)$ so the number of $b$s is at least the number of $a$s and at most twice that number. The only thing I have achieved is to get an automaton that ...
0
votes
0answers
31 views

CFG notation meaning in making LL parse table

I have problem of interpreting Context-free grammar notation in making LL(1) parse table. To make LL(1) parse table. Two rules are shown below: If A -> α is a production choice, and there is a ...
0
votes
0answers
53 views

Stuck on Converting to Chomsky Normal Form,

I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form. Here is the language: S → AA|SBBa|b A → ...
0
votes
0answers
554 views

Converting a CFG with epsilons into a DPDA

I have a CFG: S -> $T$ T -> T+T|T-T|T/T|(T)|CX|I X -> XX |C|N|_|@ C -> a|b|c|....|z|A|B|C|...|Z|_ N -> 0|1|2|....|9 I -> NI|N Here @ means epsilon. The above is a valid arithmetic expression ...
0
votes
0answers
158 views

Can two distinct strings create the same parse tree for a given grammar?

More specifically: for any arbitrary CFG, is there guaranteed to exist two distinct strings such that a leftmost parse of both strings creates the same parse tree? If not, does there exist any CFG ...
0
votes
0answers
68 views

How to see if P is decidable semi-decidable, undecidable?

I've been trying to figure out a practice exam question, about if a given $P$. $P$ is the characteristics of recursive enumerable set given as: $$P(A) = \begin{cases} ⊤ &if &|A| ≤ 100 \\ ...
0
votes
0answers
31 views

Lossless Condensing, Modification, and Decondensing

Given a string $\alpha$ that is derived from context-free grammar $G$, what is an algorithm $f$ such that there exists a string $\beta$ (derived from an unrestricted grammar) where $f(\alpha)=\beta$, ...
0
votes
0answers
58 views

Pumping Lemma to prove that L is not context free

I have the language and I want to prove that is not context-free. So I started like this: is variable. Choose w = Case 1: vxy has no c. Choose i = 2 has more a than c or more b than c. Case 2: ...
0
votes
0answers
612 views

Describe the language generated by a given context free grammar

I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction. $$\begin{align} S &\to SA \mid \epsilon \\ A &\to aS \mid bA \...
0
votes
0answers
436 views

Ogden’s lemma on CFG

I'm trying to understand Ogden's lemma, and I know there are 4 cases, but in the next example I can only find 3: Assume A = {$0^n1^m0^k$ | k = $max${n, m}} is CF: Choose z = $0^k1^k0^k ∈ A$, z = ...
0
votes
0answers
61 views

Can we say we reduced a rule if we reduced an equivalent set of smaller rules?

I have constructed an SLR(1) parsing table with the following rules. S -> S + S + S (rule 1) S -> S + S (rule 2) S -> y Is reducing rule 2, then shifting + and y, then again rule 2, equivalent to ...
0
votes
0answers
70 views

Designing CFG for sequences of words of which two arbitrary ones are reversals

Let $L$ = {$x_1\#x_2\#...\#x_k$ : $k\;\ge\;1$, each $x_i\;\in\;\{0,1\}^*$ and $\exists i,j$ such that $i < j$ and $x_i$ = $x^R_J$}. For example, $001001\#0010\#100100\#00001$ is in $L$ because $...
0
votes
0answers
148 views

Reduction CVP to CFG problem

I want to show that non-emptiness of context free language is P-complete. So, I am trying to reduce CVP to this problem by generating grammar from circuit. I consider all type of gates in circuit and ...
0
votes
2answers
69 views

Determine if the language of words with same number of 1's and 2's is context-free or not

$$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$ I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 ...
0
votes
1answer
64 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
votes
1answer
41 views

Transform grammar to Chomsky Normal Form

Question: S → abSab | baSba | TT T → aTa| bTb | ε My answer: Eliminate ε rules: S-> abSab | baSba | TT | T T-> aTa | bTb | aa | bb Correct answer: S → abSab | baSba | TT | abab | baba | T T → ...
-1
votes
1answer
28 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 ...
-1
votes
2answers
116 views

CFG for language of words with odd many $a$ and exactly two $c$

I am trying to construct a context-free grammar for the language $$ L = \{ w \in \{a,b,c\} \mid w \text{ contains an odd amount of } a \text{ and there are exactly two } c \}. $$ I am currently stuck ...
-1
votes
1answer
48 views

Set-theoretic difference of two languages in CFL - REG

Let $L_1,L_2\in$ CFL $-$ REG, with $L_1\subset L_2$. Which of the following always holds? $L_1-L_2\in$ CFL $-$ REG and $L_1-L_2\in$ REG. $L_1-L_2\in$ REG and $L_2-L_1\in$ CFL $-$ REG. $L_1-L_2\in$ ...
-1
votes
1answer
121 views

Convert CFG to CNF Arithmatic Expression

Convert CFG to CNF The Grammar E→E+T E→T T→T*F T→F F→(E) F→x Step 1 Assign variables to terminals A→ + B→ * C→( D→ ) F→x ...
-1
votes
1answer
318 views

Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 }

$L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \}$ I have trouble about this PDA. Anybody can help me about draw this PDA?
-1
votes
1answer
69 views

How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$

$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$ I don't have any idea. Can someone help me.
-1
votes
1answer
3k views

Describing language generated by grammar

S -> aSb | A | B A -> aS | a B -> Sb | b is this the language generated by this CFG? Or am I missing something?
-1
votes
1answer
996 views

Can we remove unit productions First Before removing Null productions?

My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null ...
-1
votes
1answer
2k views

Determining whether a context-free language (CFL) described by a given grammar is regular (RL)

In my homework we're given the following problem: Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps: S -> T T | U T -> 0 T | ...
-3
votes
1answer
96 views

PDA for parentheses language

Construct a PDA for the language described by the following CFG: $$ S \to [S] \mid \{S\} \mid \Lambda $$ How can I develop a pushdown automaton for this language?