Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

learn more… | top users | synonyms

2
votes
1answer
27 views

Chomsky normal form: epsilon rule

I have pretty simple question, but still can't find an answer just googling it. I'm trying to understand Chomsky Normal Form (CNF). There are three production rules: $A \to BC$ $A \to \alpha$ $S ...
0
votes
0answers
14 views

Rule Tree Question [on hold]

I was given the following assignment: http://imgur.com/GLKAlut I understand how to define the language but I'm having trouble figuring out how to draw the rule tree... Can anyone point me in the right ...
1
vote
1answer
38 views

How to check ambiguity of a specific grammar

Giving the following Grammar: S → ^ | SaSMSM | SMSaSM | SMSMSa M → b | c ^ means eopsilon. How can i check whether its ambgious or not? My intuition is ...
0
votes
2answers
50 views

Find a CFG for a language

In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y > x$, $z > w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p ...
-1
votes
1answer
34 views

Show L is not context free using the CFL pumping lemma

I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$ So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 > m$. We can decompose $z = ...
3
votes
2answers
218 views

Proving that a word is *not* generated by a context-free grammar

I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF... How did they get the answer so that ab ...
2
votes
1answer
37 views

How do you describe a language that is generated by Context Free Grammer [closed]

I am familiar with describing Regular Expressions but when it comes to describing CFG I get confused. Do you describe it in words like you would regular expressions or do you do something like this ? ...
2
votes
0answers
55 views

Good introductions to Formal Language Theory and Formal Grammars

Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover the mathematical basis of Syntax and things like context free grammars and pushdown automata. In ...
0
votes
1answer
43 views

a regular language so that $unary(L) \notin $Context Free Languages [closed]

I need a regular language $ L\subseteq \{0,1\}^{*} $ so that $unary(L)$ is not context free. unary of $L$ is defined by: $$unary(L) = \{0^{1x} : x \in L \}$$ Example $L = \{0, 11\} $ $\rightarrow ...
0
votes
3answers
145 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
1
vote
0answers
34 views

A construction to show a very restricted substitution closure result for DCFLs

Let $P$ be a deterministic PDA recognizing a deterministic CFL with a binary alphabet. Modify $P$ to identify its reading states (denote this subset of states by $R$) in accordance with the ...
1
vote
1answer
34 views

Why does left recursion have to be eliminated? [closed]

For example, Let the Grammar be: S->Sa|B Thus, S->Sa->Saa->...->Saa...aaa->Baa...aaa What's wrong with ...
1
vote
2answers
89 views

proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular [closed]

I am trying to prove this following theorem, can someone help please? Let $L$ be a language over the alphabet $\Sigma = \{ a,b \}$. If $L' = \{ w\$w^R \mid w \in L\}$ is context-free, then $L$ is ...
1
vote
2answers
99 views

Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$ [closed]

I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$ $$L=\{a^nb^m\mid 2n<m<3n\}$$
3
votes
1answer
55 views

Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

I want to show that for any language $L \subseteq \{ a \}^* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages. I know ...
0
votes
2answers
59 views

How many states when converting CFG to PDA

When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find ...
2
votes
0answers
56 views

If $L_1$ is regular and $L_1 \cap L_2$ context-free, is $L_2$ always context-free? [closed]

If $L_1$ is a regular language and $L_1 \cap L_2$ is a context-free language, does it mean that $L_2$ is a context-free language too? I attempted to prove that $L_2$ was not required to be ...
3
votes
1answer
105 views

Prove that context free languages aren't closed under DropMiddle

The question is simple: $\qquad \operatorname{DropMiddle}(L)=\{xy\in\Sigma^* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\}$. Prove that CFL's aren't closed under ...
0
votes
1answer
49 views

Can a context free grammar for $L$, generate a string not in $L$?

from Sipster's definition: Any language that can be generated by some context-free grammar (call it $G$) is called a context-free language (CFL). However, can $G$ generate strings that are not in the ...
1
vote
0answers
30 views

Prove a language is context-free [closed]

for this problem, it asks to prove that A and B are context free, however the CFL pumping lemma doesn't prove that. It proves when languages are not context free. Would the easiest way to prove ...
2
votes
1answer
47 views

Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free?

I was wondering if this language is context-free: $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ I know that this language is not regular because it fails the pumping lemma ...
1
vote
2answers
31 views

Develop the context free grammar to match this language (puzzle)

This is a puzzle type question which asks to create a context-free grammar to match this language: ...
0
votes
2answers
63 views

Proving that context-free languages are closed under inserting symbols [closed]

This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation. This means basically that any context-free language which ...
0
votes
1answer
24 views

Construct context free grammar from language

I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific: $\lbrace ...
0
votes
1answer
47 views

If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language? [closed]

If two regular languages $L_1$ and $L_2$ are both not context free languages then is $L_1 \cup L_2$ also not a context free? I am aware that if $L_1$ and $L_2$ are context free languages then the ...
2
votes
1answer
37 views

Complement DCFGs and handles

If I have a DCFG G for some language over {0,1}* and a DCFG H for its complement, with disjoint non-terminals, and a (perhaps partially reduced) string, can they both have a handle for the string? So ...
1
vote
0answers
56 views

Complexity of Languages [closed]

1) Find language $L_1 \subseteq L_2 \subseteq L_3$ such that both $L_1$ and $L_3$ are not context-free languages, but $L_2$ is a regular language. 2) Find language $L_1 \subseteq L_2 \subseteq L_3$ ...
3
votes
2answers
81 views

Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
1
vote
1answer
35 views

Proving a language is not a regular language but a context free language [duplicate]

I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$. I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is ...
2
votes
1answer
84 views

Context-free grammar for $L = \{a^n : n\leq2^{20}\}$

I want to find a context-free grammar for $L = \{a^n : n\leq2^{20}\}$. There's one for sure. I approached it by two ways and both seemed dead end. One was to set a limit during the production of the ...
3
votes
1answer
93 views

Simplification of CFG

Recently i was studying removal of useless symbols in productions given in Ullman Hopcroft. The grammar goes as follows S-> aAa | aBC A -> aS | bD B - > aBa | b C-> abb | DD D -> aDa In the ...
2
votes
0answers
38 views

What kind of structural features of strings can be described by regular grammars?

Context-free grammars, as well as other types of grammars, can naturally associate structure with the strings of the defined language, for example tree structures in the case of context-free language. ...
2
votes
1answer
41 views

CFL not closed under intersection while Turing Decidable are

It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not. Does not Turing Decidable engulf all CFLs?
3
votes
2answers
72 views

Complexity of CFG grammar for a regular language

I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages. Are there known results about the ...
5
votes
2answers
65 views

Context-free language and regular expressions

I have the following context-free language: S -> ASa | b A -> aA | a I don't understand why this is not regular. I first said that it's generated by the ...
0
votes
2answers
112 views

What Do Logical Operators In a Grammar Mean?

Is there a way to figure out what the following CFG accepts? $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid\; \thicksim p \end{align}$ ...
1
vote
3answers
94 views

Determining if a context-free grammar produces even-length strings [closed]

Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?
5
votes
1answer
77 views

How to find a Deterministic PDA for an intersection of languages

There are two languages, $\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and $\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$ where $N_a$ means the number of occurrences of $a$ in the string $w$. Same ...
2
votes
0answers
59 views

Why CFG can specify structure of sentence but Regular grammar cannot? [duplicate]

CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?
0
votes
2answers
78 views

Is $a^{n+m}b^{n}c^{m}$ context free?

Language: $ L = a^{n+m}b^{n}c^{m} $ As per a recent test I gave, this language is not context free. However, I think it is. Corresponding Grammar: $ X \rightarrow aXY \space |\space \epsilon $ $ ...
0
votes
0answers
13 views

Unambiguous Context free Grammar [duplicate]

I was reading through Context Free Grammar, and I came across ambiguous grammar. If the language produced by CFG has more then 1 parse tree, then CFG is an ambiguous grammar. Is there any way by which ...
0
votes
0answers
46 views

Is the language of words with as many a's in the first as b's in the second part context-free?

Is $L = \{ W_1W_2 \mid W_1,W_2 \in (a+b)^* , N_a(W_1) = N_b(W_2)\}$ context free? Can we construct an NPDA for the language? There is a book here that claims $L$ is not CF (without any elaboration), ...
1
vote
2answers
147 views

Closure of CFL against right-quotient with regular languages

Let $A/B$ = $\{ w \mid wx \in A$ for some $x \in B \}$. Show that if A is context free and B is regular, then $A/B$ is context free. My interpretation of this is is that we need to show that if ...
1
vote
1answer
59 views

Kleene star closure of a context free grammar

I have this question about closure of a context free grammar, and if someone can check my answer and see if it makes sense, and if not, what is missing, I would be very grateful. Give an ...
3
votes
2answers
156 views

How to get 2-state PDA for CFG?

I'm studying for my Computing languages test and there's one idea I'm having problems wrapping my head around, as far as I know for any Context Free Grammar (CFG), we can design a 2-state Pushdown ...
1
vote
1answer
35 views

Eliminating $\varepsilon$-productions during elimination of left recursion

I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any. I have the grammar $\qquad S \to Aa \mid b$ $\qquad A \to Ac \mid Sd ...
3
votes
1answer
100 views

If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

I've seen in previous exams that professors marked the theory as correct: If $L$ is CFL and $\overline{L}$ is CFL, then L is regular. I just don't see how this would work. How would we prove ...
1
vote
1answer
46 views

Is the following language context-free? $L= \{a^nb^m| m\geq2^n\}$

Is $L=\{a^nb^m|m\geq2^n\}$ a context-free language?
0
votes
1answer
130 views

Is this language context free?

In a recent test, I was asked to recognize if the below language is context free: $\qquad\displaystyle L = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$ I think it is context free, and can be accepted by ...
4
votes
2answers
300 views

Is $a^n b^n$ an artificial language or does it occur in the real world?

The classic example of a context-free grammar is $a^nb^n$. That is, $n$ occurrences of $a$ followed by an equal number of occurrences of $b$. Do such forms occur in the real world? Can you provide an ...