Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.
4
votes
3answers
95 views
Example of a non-context free language that nonetheless CAN be pumped?
So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).
2
votes
1answer
58 views
Is $L$ always context free?
Consider formal language $L$ over finite alphabet $\Sigma$ consisting of all words over $\Sigma$ that have non-trivial period (non empty prefix that is also a suffix). Is $L$ always context free?
...
2
votes
1answer
59 views
PDA for this context-free grammar
I have the following CFG $G$:
$$ \begin{align}
S &\rightarrow aAbb \mid aaBb \\
A &\rightarrow aAbb \mid \epsilon \\
B &\rightarrow aaBb \mid \epsilon \\
\end{align} $$
I have to create a ...
1
vote
2answers
65 views
Easiest way to write a grammar?
When I see a problem like "Write a grammar for a language $L$ if $L = \{..\}$" for me is a matter of "instinct" the way that one can define productions. For example given the following exercise:
...
0
votes
0answers
29 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
1answer
27 views
Weak Precedence Grammar and Parsing
I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation?
Any ...
0
votes
2answers
99 views
How to take complement of a language?
I'm stuck on this question about context-free languages and was hoping for some clarification.
$\qquad L = \{a^i b^j c^k \mid i=j, i=k\}$
is not context-free. Show that its complement is ...
2
votes
2answers
113 views
Is {xyx | |x|≥1} context-free?
Is $L=\{ xyx \mid x,y \in \{a,b\}^* \text {and } |x| \ge 1 \}$ context-free?
If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping ...
0
votes
1answer
67 views
Proving that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not context-free
How can I prove that $\{0^n 1^{n^2} \mid n \in \mathbb{N}\}$ is not a context free language?
I tried to prove it using the pumping lemma, but I don't know how to deal with the case when $vxy$ ...
5
votes
1answer
56 views
prove no DPDA accepts language of even-lengthed palindromes
How do you prove that the language of even-lengthed palindromes, i.e.,
$L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton?
Is ...
10
votes
0answers
205 views
Is this strange language context free?
Is the following language context free: $L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^*\text \{ \epsilon \} \ ,\ \mid u \mid = \mid v \mid \ , \ u \not= v \ , \ \mid x \mid = \mid y \mid \ , \ x \not= y \ ...
2
votes
1answer
65 views
Prove that context free languages are not closed under swapping prefixes and suffixes
Prove that context free languages aren't closed under this operation: $ A(L) = \{ zyx \mid x,y,z \in \{0,1 \}^*, xyz \in L \} $
Obviously, we need to find a context free language $L$ such that $A(L)$ ...
1
vote
2answers
97 views
Converting CFG to PDA
I have the following CFG,
$S \rightarrow CB$
$C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$
$B \rightarrow AB \text{ }|\text{ } \varepsilon$
$A \rightarrow a\text{ }|\text{ }b$
...
2
votes
1answer
105 views
Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?
Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free ?
If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \} $ is ...
1
vote
1answer
54 views
Is the intersection of two context free languages recursively enumerable?
I read a quotation attributed to Sheila Greibach that says that the intersection of two context free grammars is recursively enumerable.
I could not, however, find a citation for this quotation (and ...
1
vote
1answer
32 views
Questions about an answer to a pumping lemma question for CFLs
In the answer to this question, I'm not understanding how the string is derived for a given $l$.
For example,
Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} ...
2
votes
0answers
30 views
The grammar of the GeoQuery language
GeoQuery is a dataset used for benchmarking semantic parsers. It contains 880 queries about USA geography. The queries are in Prolog format, for example:
...
3
votes
1answer
54 views
Are permutations of context-free languages context-free?
Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ ...
2
votes
2answers
81 views
Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state
I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question.
The question states that the PDA has at most 2 states. Clearly 1 will ...
0
votes
2answers
49 views
Proving $\{xx^R \mid x\in L_1, x^R\in L_2\}$ is context-free
I have this problem:
Let $L_1$ and $L_2$ be two regular languages. Show that $L_3 = \{xx^r : x \in L_1, x^r \in L_2 \}$ is a context-free language.
I am unsure how to prove that some language ...
8
votes
1answer
198 views
Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?
Is the language $ L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free ?
I guess that it's not context free because it seems too complicated for a PDA to decided whether 2 numbers ...
0
votes
0answers
15 views
Pumping Lemma on CFL Problem [duplicate]
I have laid out the various cases that would make this not a context free language already and proved all but one for this set:
\begin{equation}
A = \{a^f b^g \mid f = g^2\}
\end{equation}
...
3
votes
1answer
87 views
How to find the pumping length of a context-free language?
Please help me understand, and if possible, tips, to determine a pumping length $p$.
Suppose I have the example :
Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,C\}$, set of ...
0
votes
1answer
63 views
Convert CFG to PDA
Is there any set of rules or methods to convert any context free grammar to a push down automata?
I already found some slides online but I wasn't able to understand them.
In slide 10 he speaks ...
0
votes
0answers
27 views
Is this Chomsky Normal form correct? [closed]
Here is my approach, am I right?
Chomsky Normal Form solution for a problem
Here is my attempt at CNF,
...
4
votes
1answer
44 views
Closure under intersection of context free binary trees
Some sets of ordered binary trees can be represented as a CFG with rules of the form
A -> aBC
A -> b
Where A,B,C are ...
6
votes
1answer
103 views
Are context-free languages in $a^*b^*$ closed under complement?
The context-free languages are not closed under complement, we know that.
As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
4
votes
2answers
112 views
Why is the following language not context-free?
$L = \{a^n b^m | m \not= n^2 \}$
I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck.
Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
0
votes
1answer
35 views
CFG for $\{a^i b^j : 2 i<j\}$ [duplicate]
So I have a question:
Give a CFG for $\{a^i b^j : 2 i<j\}$
And this is my approach:
$S\to AB$
$A\to aAb\mid \varepsilon$
$B\to b \mid bB$
A confirmation, or correction, along with how you ...
4
votes
2answers
102 views
Two-State Turing Machine for Parenthesis Matching
In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet ...
3
votes
2answers
52 views
Give CFG and PDA for the words that start and end with the same symbol
I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
1
vote
1answer
51 views
How can I show a linear languages are closed against concatenating with regular ones?
This was given as a homework problem but I have already submitted the assignment. I'd like to resolve it at this point for my own satisfaction.
Given that $L_1$ is a linear language and $L_2$ is a ...
3
votes
2answers
111 views
A pumping lemma for deterministic context-free languages?
The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden's lemma) can be used to prove ...
2
votes
2answers
73 views
Context free grammar construction
My problem with CFG is, I am to generally create ones that don't have requirements such as:
$\qquad \{a^m b^n \mid m \le n \le 2m \}$
I have no clue where to begin, and how to approach it. I was ...
1
vote
0answers
68 views
CFG to CNF conversion steps
I could find that different texts follow different steps in the conversion of CFG to Chomsky Normal Form. I couldn't find any presumptions they made in the conversion steps. I have some questions ...
2
votes
2answers
125 views
Pumping lemma for CFG doubt
I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought ...
1
vote
2answers
49 views
How to write Context Free Grammar with numerical restrictions
I am supposed to write a Context free grammar that generates the language:
$\qquad L(G) = \{0^{3n}1^{2n}0^{m}1^{m} : n \ge 1, m \ge 1\}$
I have the rules:
$$S \rightarrow 000S$$
$$S \rightarrow ...
-2
votes
2answers
64 views
A problem on first and follow sets of a grammar
Let me know the first and follow sets of the following grammar, also the explanation to it
$A \to Ba \mid Aa \mid c$
$B \to Bb \mid Ab \mid d$
Non-terminals: $\{A,B\}$
Terminals: $\{a,b,c,d\}$
-1
votes
1answer
29 views
Show that if L ⊆ {a}∗ is a CFL, then L is regular. [closed]
How can I Show that if L ⊆ {a}* is a CFL, then L is regular?
0
votes
1answer
59 views
How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ? [closed]
How are these Context-Free Pumping Lemma Approaches differ?
Maybe this might help understand pumping lemma better
$(a^{i}b^{i}c^{j}d^{j} \mid i, j \geq 0$}
$(a^{i}b^{j}c^{i}d^{j} \mid i, j \geq 0$}
...
2
votes
2answers
65 views
Why is the subset of palindromes of a regular language context-free?
Why is $A(L) = \{x \in L \mid x = x^R \}$ context-free if $L$ is a regular language?
Trying to understand the approach to determining whether a regular language is context-free.
1
vote
1answer
71 views
Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?
$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $
Is this language a context free language?
If yes give a PDA. If no, give a proof.
The pumping lemma for context free languages doesn't seem to work ...
5
votes
2answers
92 views
Finding the language generated by a context-free grammar
This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):
What language is generated by this grammar?
$S \rightarrow a S b S ...
1
vote
2answers
82 views
Grammar for describing boolean expressions with AND, OR and NOT
I wrote the following LL(1) grammar to describe the set of boolean expressions involving AND ,OR an ...
-1
votes
1answer
112 views
Is the following grammar ambiguous?
Is the following grammar ambiguous and how would you justify it?
$G=(\{ S,A,B \}, \{a,b\},\{S \to aA, A \to BA \mid a, B \to bS \mid cS\}, S)$
2
votes
2answers
67 views
The importance of normal forms like Chomsky normal form for CFGs
I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't ...
1
vote
1answer
59 views
Is the following language context free?
Is $L = \{ a^nb^nc^j \mid n \le j\}$ a context-free language? I'm getting really stuck generating a grammar for it. Any help would be appreciated.
3
votes
1answer
77 views
Proving that a specific language is a CFL, and that another language is not a CFL
I have two languages $C_1$ and $C_2. \left(\Sigma=\{0,1\}\right)$:
$C_1=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$, and $C_2=\left\{xyz\mid x,z ...
0
votes
1answer
32 views
CFG using the set $L =\left\{{a,b}\right\}$ for the expression $a^{m}b^{n}$, where $m \neq n$ [duplicate]
I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$.
This is what ...
1
vote
1answer
56 views
CFG to Chomsky normal form
I've read this part like 3-4 times and I'm not understanding what is going on.
Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The ...
