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
0answers
3 views

How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A

Let us consider the following Context-Free Grammar G = ({S,A,B,C,D},{a, b}, S, P) with production rules P: S → SSA | Bb A → BSA B → A | Cb C → AD | Cb | ɛ D → a | b | ɛ Let L be the language ...
0
votes
2answers
17 views

PDA with more than one initial state

I'm wondering if PDAs with more than one initial states are also accepting context free languages. If found that question on this site about NFAs and would like to know if this answer is also valid ...
-1
votes
0answers
12 views

How to say if this grammar is LL(1)?

I need some help with understanding if a grammar is $LL(1)$ or not. $$ \begin{align} S \rightarrow AB\\ A \rightarrow a \mid \varepsilon \\ B \rightarrow bCd\\ C \rightarrow c \mid \varepsilon \end{...
-1
votes
1answer
25 views

Grammar with a long derivation generates an infinite language

Let $G$ be a CFG in Chomsky normal form that contains $b$ variables. Show that if $G$ generates some string with a derivation having at least $2^b$ steps, then $L(G)$ is infinite. This question is ...
1
vote
1answer
21 views

CFG for a given languague

Give a CFG for the languague L = $ \{ 1^n +1^m = 1^{n+m}| n,m \in N_{0}\} $ , with the alphabet $\Sigma =\{1,+,=\}$. I am currently trying to solve the given task, I thought a good way is to split ...
1
vote
1answer
24 views

How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma?

I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $a^{n^2}b^n$. If you divide it into $uvwxy$ and have only $a$'s in $v$ and ...
3
votes
3answers
75 views

$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $ is context free language

Let $\mathcal{L}$ be context free language over alphabet $\Sigma$. Define $\mathcal{G}$ as $$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ ...
0
votes
1answer
34 views

What is context free grammer of $L = \{w: n_c(w) \ne n_a(w) + n_b(w)\}$

I can't find out how to find a context free grammar for bellow language, is there any specific way to solve that? $L = \{w: n_c(w) \ne n_a(w) + n_b(w)\}$
0
votes
1answer
27 views

context free grammar of given language

I wonder how can I find out what is context-free grammar of the following language? $$ L_4 = \{w_1\#w_2 \mid w_1,w_2 \in \Sigma^*, w_1 \neq w_2^R \} $$
0
votes
2answers
64 views

Context free grammar for $A \circ B$

If A and B are regular language, what is a context free grammar of the following language? $$ A \circ B = \{ xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y| \} $$
0
votes
0answers
25 views

Making context-free grammar unambiguous

I'm trying to change below context free grammar such that it becomes unambiguous, but I don't know what steps I should take. Is there any specific way of doing that? Here is my CFG: \begin{align} &...
1
vote
1answer
39 views

Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$

I try to find a context free grammar for the language $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$. There is a hint ...
0
votes
1answer
36 views

what is CFG of $\{a^i b^j c^k \mid k = |i-j| \}$

what steps should I take to find out what is the context free grammar of $L(w) = \{a^i b^j c^k \mid k = |i-j| \}$
-1
votes
1answer
24 views

Context free Grammar for x1#x2#…#xn

Design a Context-free grammar (CFG) for this language
0
votes
2answers
60 views

Is the following language is a context free grammar language?

The question is to determine whether L is a context free grammar language, what do you think?
0
votes
0answers
41 views

generate CFG from words that have even length and have at most two 0's

How to I generate a CFG from the language that have even length and have at most two 0’s L3 = {w ∈ {0, 1} ∗ | w is even length, 0<=2 } I feel stuck on meeting the criteria of maximum two 0s My ...
0
votes
1answer
28 views

How to show that Language is not Context Free?

There is a question to show that $L=\{a^{n!} \mid n \geq 0 \}$ is not regular using Pumping Lemma. However, I have the answer in the book which is found to be somewhere wrong. I am sharing the ...
2
votes
2answers
79 views

Unambiguous context-free grammar for strings with at least as many a's as b's

I have designed this Grammar but it is ambiguous: $$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$ Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.
0
votes
0answers
40 views

Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?

I am supposed to find an algorithm solving the following problem: Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$. ...
-2
votes
1answer
32 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?
1
vote
1answer
18 views

Language of particular CFG

Let: $ G = <V, \Sigma, R, S >: \\ V = \{ S,A,B,C \} \\ \Sigma = \{0, 1\} \\ R: \\ S \to CSC|A \\ A \to 0B1|1B0 \\ B \to CB|\epsilon\\ C \to 1|0 $ I need to find the language (no need to ...
-1
votes
2answers
21 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
vote
3answers
41 views

What does “Every CFL is decidable” exactly mean?

I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means. I know that generation of a particular string by a given CFG is a ...
1
vote
1answer
37 views

Use or Importance of $\Rightarrow^*$ operator

Particularly, there are 2 variants of $\Rightarrow$, one is $\Rightarrow^*$ and another is $\Rightarrow^+$ which are used in derivation of strings using the productions of the grammar. As stated here,...
3
votes
1answer
36 views

Is the language of palindromes context-free?

Is the language $\{ w=w^R \mid w \in \{0,1\}^* \}$ a context-free language? I am confused in deciding whether the language is context-free or not, that is one of my problems, I do a pumping lemma ...
0
votes
1answer
19 views

How do I calculate the probability of a PCFG rule in a parser?

I'm quite struggling with calculating the probability of a rule for a PCFG. I've been looking for examples online and more information, but I am none the wiser. Here is an image of the slides. I ...
-1
votes
1answer
35 views

How do I convert this PDA to CFG?

How do I convert this PDA to CFG? I am currently stuck with this, any help would be appreciated, thank you in advance!
0
votes
1answer
31 views

The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ...
0
votes
0answers
19 views

Grammar for $\{a^n b^m c^{n+m} \mid n,m \ge 1\}$ [duplicate]

Please help me solve this problem: Design a grammar for the language $\{ a^n b^m c^{n+m} \mid n,m\ge 1\}$.
-1
votes
1answer
38 views

CFG for this language $\{a^k b^m c^n \mid 1 \leq k, m, n, n \leq 2k\}$ [duplicate]

I'm kinda new in this topic and I don't know how to figure out the rules to make a CFG out of this language, if anyone could give me an idea or hint so I can try to solve it knowing that, I would be ...
2
votes
1answer
102 views

Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?

I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ...
0
votes
1answer
24 views

A grammar for my context free language {xy | x, y ∈ {a, b} ∗ , |x| =|y| , x != y}

This question is given as an exercise to me . I took a look at the solution given by the instructor which is not the same as my solution . So I thought it would be wise to ask it here considering ...
0
votes
1answer
30 views

How can I determine the start non-terminal of a CFG?

Suppose I have a grammar such that there exist $n$ production rules which contain only terminal symbols, and none of these rules produce the same terminal (disjoint). $A ::= x|y|z$ $B ::= a|b|...
0
votes
1answer
40 views

What is “σ” in a context free grammar?

I have a grammar like this: A → BAB | B | ε B → 00σ | ε What is the meaning of σ in the second rule?
1
vote
2answers
68 views

Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$

I would like to ask for intuition to understand the difference between a CFG generating $\Sigma^*$ and a regular grammar generating $\Sigma^*$.. I got the examples here from Sipser. Let $ALL_{CFG}$ ...
0
votes
1answer
22 views

CFG for $w\#x$ where $|w| = |x|$ and $w \neq x^R$

How do I construct a context-free grammar for the following language? $$L = \{w\#x \mid w, x \in \{0, 1\}^*, |w| = |x|, w \neq x^R \} $$
0
votes
2answers
33 views

How to prove this language is context free?

There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free. $L = \{a^{(n+1)} b^{(...
1
vote
1answer
21 views

Unambiguous grammars with different right and left hand derivations

I read recently that for an unambiguous grammar the left hand derivation need not necessarily be equal to the right hand derivation. Can someone give an example of this?
0
votes
0answers
28 views

Is there a pda with maximum 3 state for every CFL?

This is the first question I'm asking here I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?
0
votes
0answers
15 views

How can I create the context free grammar for this language? [duplicate]

I need help finding the context-free grammar for this language. $$ L = \{a^ib^jc^k \in \{a,b,c\}^* \mid \text{$i,j,k \geq 1$, and $i=j$ or $i=k$ or both}\}. $$ I've found a way to satisfy $i = j$ ...
0
votes
0answers
31 views

how to write a language for context-free grammar generates the empty string?

How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?
1
vote
1answer
36 views

How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?

This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3. $$ \text {Let }b_i \text{ denote } i \text{...
-1
votes
1answer
29 views

What is the language generated by this grammar?

I'm struggling to find the language generated by the following grammar: Any help would be appreciated.
0
votes
1answer
23 views

Context-free grammar for language involving multiplication

I'm struggling to find the context-free grammar for the following language: $$ L = \{a^sb^tc^m:s,t,m\in\mathbb{N}^+\land1\leq t\leq3\land s\times t=m\} $$ Any help would be appreciated.
-1
votes
1answer
24 views

Find CFG for the following language

I need to show that the following language is context free: $$L = \{a^\ell b^n c^m | \ell, n, m \in \mathbb{N}^+ \wedge ((\ell \ge n) \vee (\ell \ge m))\}$$
0
votes
0answers
26 views

Context free grammar Help

I need to create a CFG for the following language: $$ \{a^ib^jc^k|i≤j≤2i, k=2j\} $$ Getting the a's and c's to be correct is easy enough but everything else is confusing me slightly. any help would ...
1
vote
0answers
21 views

CFG to CNF, but stuck on the last few steps

I recently learned about the conversion, but I seem to be stuck. I need to convert the following CFG to CNF: $S → XY$ $X → abb|aXb|e$ $Y → c|cY$ There is no S on the right side, so I did not need ...
0
votes
0answers
16 views

Proof that $L = \{w | na(w) + nb(w) = nc(w)}\ is not regular [duplicate]

So.. my professor mentioned that it has something to do with $Wi = a^5b^i$ $Zij = c^(i+5)$ which is in the language But then mentioned that $Wj = a^5b^j$ $Zij = c^(i+5)$ Is not in the language, ...
1
vote
2answers
51 views

Is my grammar correct and context free?

I have this language $L = \{a^{n}b^{3n}c^{2m} : m,n \ge 1\}$. I have to determine a free context grammar that generates L. Looks easy BUT i have a question about the grammar I found. First things ...
0
votes
1answer
32 views

How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$

Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s. Also, I have a hint HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...

1
2 3 4 5
26