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
votes
0answers
6 views

define a context-free language( CFG ) that can accept one or more initial symbols [duplicate]

define a context-free language( CFG ) that can accept one or more initial symbols. Points that need to define are: what language it generates how it accepts and everything necessary to make it work
1
vote
0answers
11 views

What to do with operators with the same precedence in an unambiguous grammar?

I'm trying to create an unambiguous grammar for a calculator that uses $+$, $-$, $*$, $/$ and $()$. From watching videos and reading articles online, I understand how to create the grammar with $+$, $*...
-4
votes
0answers
24 views

6. Construct the PDA for the language L ={aibjck, with j=2i or j=2k and i,j,k≥0} [duplicate]

Construct the PDA for the language L ={aibjck, with j=2i or j=2k and i,j,k≥0}, how can we did it i tried but it is difficult
-1
votes
0answers
31 views

Construct the PDA for the language [duplicate]

Construct the PDA for the language $L =\{a^i b^j c^k, j=2i \text{ or } j=2k \text{ and }i,j,k\geq0\}$
-4
votes
0answers
38 views

How to remove epsilon production from this Context Free Grammar?

I want to remove the epsilon production from the following grammar: S → [ S ] | SS | ε
0
votes
0answers
38 views

Eliminating ambiguity in $A \to AA \mid (A) \mid a$

I'm trying to solve this complier design problem related to ambiguity in CFG the given grammar is \begin{align} &A → AA \\ &A → (A) \\ &A → a \end{align} I was able to find that this ...
1
vote
0answers
36 views

Different PDA design processes — both valid?

This video shows how to design PDA from a CFG: https://www.youtube.com/watch?v=ZImtQBMSW_Y Basically, we always have 4 basic states, and one of them is a "hub" for loops that implement ...
1
vote
2answers
29 views

Converting a regular expression to a context-free grammar

Does this conversion look right? I am learning conversion from RE to CFG. RE: $$(a \cup b)^* \cup ab(a \cup b)^*$$ CFG: Terminals: $$ S_1 \to a \\ S_2 \to b $$ This is for the first $(a + b)^*$: \...
1
vote
0answers
26 views

Generating a recursive descent parser for grammar having Kleene star

From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar: \begin{align} &E \to E+T \mid T \\ &T \...
0
votes
0answers
25 views

Is this a regular language + context free [duplicate]

Is $L_1 = \{0^n1^m0^{n+m}\mid m,n \geq 0\}$ regular? What is its context free grammar and proof? Second, is the following language context-free? $$L_2=\{0^a1^b2^c \mid a,b,c \geq 0 \text{ and } c = ab+...
1
vote
1answer
19 views

Pumping lemma for an involved non context free language

Hi I'm trying to show $C=\{wzzw^R|w,z\in\{0,1\}^+\}$ is not a context-free language.( I have this believe because $C=\{ww|w\in\{0,1\}^+\}$ is not a context free language.) I'm really struggling to ...
-1
votes
1answer
51 views

Is this language a context free language?

Consider the following language, where the alphabet is $\{0, 1, 2\}$: $B = \{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\}$. Is this language a context free language? Prove your answer. I am ...
1
vote
2answers
42 views

PDA accepting all words not of the form $b^na^n$

I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages. If I have context-free ...
3
votes
2answers
496 views

Given L is a regular language, prove that Perm(L) is Context-Free

Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\}, $$ where $perm(x)$ is the set of all permutations of the ...
1
vote
1answer
50 views

Exclusion in a context-free language?

I am learning automata theory, and I am confused about this exercise: Give context free grammar to create the following language where the input alphabet is $\{a,b\}$ $L = \{w \text{ where }w\text{ ...
1
vote
1answer
28 views

Grammar for all words other than $wq,qw$

I want to generate a grammar that can't generate the words $qw$ and $wq$ but can generate the word $qwwq$. In other words, $L(G)=\{m ∈ \{q,w\}^* \mid m \neq wq,qw \}$. My grammar: \begin{align} &S ...
3
votes
2answers
36 views

Language equivalency for modified CFG closed over intersection

Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both ...
0
votes
1answer
22 views

Words which, cyclically shifted twice, equal their reverse

Let the alphabet be $Σ = \{0, 1\}$. For any string $w ∈ Σ^*$ of length at least 2, define the operation $C_2(w)$ to be a cyclic shift of size 2 on $w$. That is, if $w = w_1w_2 \cdots w_n$ with $n ≥ 2$ ...
-1
votes
0answers
18 views

Show that if A is context-free and B is regular, then A ÷ B is context-free [duplicate]

For languages A and B over Σ, define the language A ÷ B as follows: A ÷ B = {w ∈ Σ^∗: there exists x ∈ B such that wx ∈ A} Show that if A is context-free and B is regular, then A ÷ B is context-free.
1
vote
1answer
59 views

Construct a grammar for $\{a^n(bc)^m : m,n \ge 1, m < n/2\}$

I'm new to writing languages in context-free or regular grammar, so I'm struggling how to do this one. It is a bit more complicated that simpler ones I've practiced doing. The problem is to construct ...
0
votes
1answer
62 views

Is the following language regular; context-free but not regular; or not context-free?

Let $\Sigma=\{0, 1, \#\}$. Is the following language regular; context-free but not regular; or not context-free? Justify your answer $$L=\{x\#y :\ x, y \in\{0, 1\}^∗\text{ and }\operatorname{bin}(x) + ...
1
vote
1answer
32 views

Given CFG generates all words with equally many 0s and 1s

Here is an exercise from an introduction to computation class: Show that the following context-free grammar $G$ generates the language $L$ of words over $\{0,1\}$ with an equal number of $0$s and $1$...
1
vote
2answers
40 views

Relation between programming languages requiring declaration of variables before use and using the token class $\text{id}$ while parsing

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al. where I came across the following excerpt. Example 4.11. Consider the abstract language $L_1 = \text{ { $wcw$...
1
vote
1answer
105 views

Constructing a context-free grammar

I want to design a context-free grammar that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, ...
1
vote
1answer
189 views

How to prove the language of contractible strings is context-free but not regular?

How to prove this language is context-free but not regular? I can't figure out it. A string is contractible if there is a sequence of contractions which result in the empty string, where a ...
2
votes
0answers
21 views

Generating an “approximate” grammar

This is my first time posting here, so I hope I'm on topic. I have a table of natural-language data of the form ...
0
votes
0answers
23 views

How to change a grammar so that it can be unambiguous?

The original grammar is $$ S \to SaS \mid SbS \mid ScS \mid d $$ My answer is $$ S \to daS \mid dbS \mid dcS \mid d $$ Is that correct?
0
votes
0answers
16 views

L= ${ a^mb^nc^pd^q: m+n<>p+q }$ context free? [duplicate]

I cant find the grammar to prove it is context free but. I also tried a PDA but couldnt make it. Can someone suggest a grammar for this?
1
vote
0answers
30 views

How to generate a context-free grammar that defines a regex expression

As the title says, I have been asked to generate a grammar that defines the language of regular expressions. The symbols are: + . * | ? char I tried and came up with this but it doesn't work when ...
0
votes
1answer
49 views

Which of the following words is in the language of the grammar G?

This is taken from a practice quiz by my university. I ruled out that aabbbaab is not part of the grammar: S → aSb → aaSbb... This shows that I can't make this word because it would have to have ...
0
votes
1answer
45 views

How can I make the following grammar unambiguous

Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -> S + S | S − S | S ∗ S | S / S | (S) | x | y My attempt: ...
0
votes
1answer
25 views

CYK algorithm in theory of computation

For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n. Doubt: I marked it false in a national level exam.I think it should be any null-free context ...
0
votes
1answer
19 views

CFG of all regular expressions over a binary alphabet

I'm working on creating a rather difficult CFG and I am getting stuck on finishing it. The CFG in question is meant to contain all valid regular expressions using the alphabet {0, 1, (, ), *, +, e} (e ...
2
votes
0answers
15 views

Unparsing an operator grammar in the face of ambiguity

I'm using the grammar scheme of Danielsson and Norell ("Parsing Mixfix Operators"). The short version is: user defined mixfix operators such as _+_ or <...
1
vote
1answer
44 views

Is the language of all words of the form $wxw^Rx^R$ context-free?

Is the language $\{wxw^Rx^R \mid w,x \in \{0,1\}^* \}$ context-free My thoughts, Let $x = \epsilon$ and we get $ww^R$, which is context-free. Hence the given language must be context-free. Am I right?
1
vote
1answer
57 views

Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free

I have a question about the pumping lemma for context-free languages. I understand the conditions of the pumping lemma. Assume $L$ is context-free. Let $n>0$ be the pumping length given by the ...
0
votes
0answers
18 views

generating strings from this formal grammar [duplicate]

Hey guys I am having trouble generating strings from this language, I haven't seen a grammar that looks like this and can't figure how to generate strings from this grammar, is this Context Sensitive ...
1
vote
0answers
52 views

A Formal Grammar: defining English counting numbers?

I would like to define a grammar that produces and recognizes the counting numbers of the English language. I created the production rules below based on the assumption this is context-free, but I am ...
1
vote
1answer
24 views

Given a CFG G (in Chomsky normal form) and a string w, determine whether w has more than one parse tree in G in polynomial time

So I have the following language: C = {<G,w>|G is a CFG in Chomsky normal form and w has more than one parse tree in G} How to prove that this language is in P (decidable in deterministic ...
2
votes
1answer
44 views

Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL

I want to prove that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a Context Free Language. so far, I tried to find a Context Free Grammar for $L$ or to use properties of Context Free ...
1
vote
1answer
32 views

Difference between $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ and $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $

Is there any difference between saying $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ with $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $? I know that for $v = abab$ we have $v \in L_1$ and $v \in L_2$ my ...
1
vote
1answer
30 views

Working of PDA for $\{a^m b^n c^k \mid m=n \text{ or } n=k\}$

I understand that the language $L = \{ a^mb^nc^k \mid m=n \text{ or } n=k \}$ is context-free because it can be represented as the union of $L_1 = \{a^mb^mc^k\}$ and $L_2 = \{a^mb^kc^k\}$, which are ...
0
votes
1answer
41 views

Computing FOLLOW sets of left recursive grammar

Left recursive ambiguous expression Grammar: $E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$ I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
1
vote
1answer
61 views

Can you reduce every decidable language to a regular language?

One of my previous questions on an exam was the following Can you reduce a decidable language to a given regular language? (decidable language $\leq _m$ regular language). If so, does this mean that ...
2
votes
4answers
79 views

If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular So far I know that: There are examples where $L$ ...
1
vote
2answers
1k views

Are all finite languages context-free?

As far as I know, finite languages have a finite number of strings or words, while context-free languages are generated by context-free grammars. I don't know which aspect should I know that they are ...
1
vote
2answers
62 views

Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

I have found an exercise where it tasks to provide a grammar and a pushdown automata for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$ While finding a pushdown automata for it is quite easy (four states and two ...
1
vote
3answers
57 views

Regular Expression for language [duplicate]

I have a grammer with the following productions, S -> aA | bC | b A -> aS | bB B -> aC | bA | a C -> aB | bS I have to construct regular expression for ...
1
vote
2answers
186 views

Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')

I am trying to remove ϵ rules from the following grammar (after applying the remove redundant symbols algorithm): $G = (\{S,A,B,C\},\{0,1\},P,S)$, where the productions are \begin{align} &S \to AB ...
1
vote
1answer
55 views

Number of sentences and sentential forms generated by a grammar

In this question, I'm considering only "finite grammars". A finite grammar can only produce a finite number of distinct sentences. The following grammar is finite in my definition: ...

1
2 3 4 5
29