All Questions
Tagged with formal-languages context-free
648
questions
2
votes
4answers
53 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
39 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
47 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
20 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
33 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
64 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
22 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
19 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
32 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
32 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
87 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
305 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
39 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
38 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
42 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
69 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
95 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 \...
1
vote
1answer
41 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
48 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
31 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
108 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
50 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
59 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
496 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
36 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
472 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
31 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
65 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
42 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
107 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
33 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
34 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 ...
-2
votes
1answer
68 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
55 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
115 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 ...
1
vote
1answer
51 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
2answers
68 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
44 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 ...
1
vote
1answer
23 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
82 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 ...
3
votes
1answer
58 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
55 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 ...
1
vote
2answers
112 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
2answers
39 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
34 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
36 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?
