All Questions
Tagged with formal-languages context-free
660
questions
-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 ...
3
votes
2answers
495 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{ ...
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
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 ...
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?
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: ...
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 ...
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 ...
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
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
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:
...
0
votes
1answer
25 views
Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?
How is it possible to prove whether the language $\{a, b\}^{∗} \setminus \{S → ε, S → aSbS\}$ is context free?
1
vote
1answer
44 views
Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$
I would like some help for the computation theory.
There is a PDA that accepts the language $\{0^n 1^a 2^b \mid n = a+b\}$, so how can I express it into context free grammar? Any help would be ...
0
votes
2answers
81 views
Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?
Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free?
If so, can there be a pushdown automaton described for it?
If not, does the pumping lemma apply?
0
votes
1answer
29 views
Can PDA accept only by final state without finish reading input?
I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
0
votes
1answer
30 views
Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$
Given the following language, I am tasked with giving a context-free grammar that generates it.
$\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$
Would this be correct?
$A \rightarrow aaaA$
$B\...
0
votes
1answer
38 views
Formal proof of language accepted by a specific CFG
Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules:
\begin{align}
&S \to aS \mid B \\
&B \to abBc \mid \epsilon
\end{align}
Please provide a formal proof for the following ...
0
votes
0answers
14 views
Having trouble understanding how to prove a language context free? [duplicate]
I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
0
votes
1answer
34 views
Is this an unambiguous CFG that is not LR(k) for any k?
The grammar is this:
$$S \rightarrow a B c $$
$$B \rightarrow b B b $$
$$B \rightarrow \epsilon $$
The LR(1) states that I worked out were these
$$(1)$$
$$S \rightarrow .aBc$$
$\\\\$
$$(2)$$
$$S \...
3
votes
0answers
112 views
is it decidable whether a grammar in Chomsky normal form has useless rules?
Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
4
votes
1answer
315 views
Undecidability of “is this CFG prefix-free?”
I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition).
Another thread has the very different question "...
1
vote
1answer
66 views
How to find the language of a CFG from Production rules
I'm having problems in finding language of the CFG from given production rules. For example if the production rules are
\begin{align}
&S \to AS \mid \epsilon \\
&A \to aa \mid ab \mid ba \mid ...
0
votes
0answers
18 views
Do the SLR and LALR parsers of a same CF grammar have the same shift actions?
In theory, given that:
The LALR parser can be constructed by merging LR(1) states with the same core;
If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$;
...
3
votes
0answers
44 views
BNF rule to regular expression
I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression.
(With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
1
vote
2answers
47 views
The intersection of 2 CFL
I have the following two CFL: $A =\{a^m b^n c^n\}$ and $B = \{a^m b^m c^n\}$.
I don't understand why the intersection of this languages is $\{a^n b^n c^n\}$: can anyone explain to me why the power is ...
1
vote
1answer
83 views
Correct application of the CFL Pumping Lemma
I came across this question about showing that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable ...
0
votes
1answer
101 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
48 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 ...
0
votes
0answers
51 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
32 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^...
3
votes
1answer
125 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 ...
3
votes
0answers
57 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 ...
0
votes
0answers
63 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-...
2
votes
2answers
579 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 ...
2
votes
1answer
37 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 ...
14
votes
1answer
504 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
65 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 $\...
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
80 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
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
vote
1answer
35 views
Designing CFG that accepts $b^m a^n$ ($m ≤ n$)
I am trying to design a CFG that generates the language $\{a^k b^m a^n a^k \mid m \leq n\}$. However, I am having trouble with the $b^m a^n$ where $m \leq n$. How do I solve this?
2
votes
1answer
119 views
When our two-state PDA constructed from CFG is non-deterministic PDA?
We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
-1
votes
1answer
34 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
53 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 ...
