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

learn more… | top users | synonyms

0
votes
0answers
12 views

Pumping Lemma for CFG - How to do it?

I'm literally so confused on how to even start this problem of proving that the given language is not Context Free. L = {a^i b^j c^k d^l | i = k and j = l} I ...
1
vote
1answer
27 views

Construction of a counter automaton for the complement of the palindromes

How would I go about constructing a nondeterministic 1-counter automaton for the language $L$ that is the complement of the palindromes $\overline{L}=\{ww^{rev}\}$ over a 2 symbol alphabet $\Sigma = ...
0
votes
0answers
45 views

Why is this language is not context-free? [duplicate]

Anyone could apply some theorem to prove this is not context free? I read lot's of material. it's not homework, it's not exam, it's not anythings. I want to learn, if some people try to answer this ...
0
votes
2answers
70 views

Intersection of a language with a regular language imply context free

Lets say you have a language $L$ and you want to determine if it is context free. Context free languages intersected with regular languages are context free. Is that enough to prove that $L$ is ...
-1
votes
2answers
68 views

Complement and Context Free Surprising

Anyone can describe why $L_{1}$ is not the complement of $L_{2}$, and why $L_{2}$ is not context free? $$L_{1}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} \neq w_{2}\}$$ $$L_{2}= ...
-1
votes
1answer
50 views

Some Algorithm on Decidablitly [closed]

Anyone could correct me that Why just (1) is False. i'm not sure why others are true: ( G is a Context Free Grammar). any brief description? There is an algorithm that decides whether the ...
0
votes
1answer
36 views

What kind of subset any class of languages may or may not have?

There are different class of languages, regular,CFL, recursive and r.e. and non-r.e. Clearly a language is set of strings. if an infinite set belongs to any of these classes then what can we say about ...
0
votes
2answers
25 views

Erasing $\epsilon$ production from CFG

I would like to delete the $\epsilon$-production from the context free grammar with the following rules P: $$S \rightarrow ASB , BSA, \epsilon$$ $$A \rightarrow aS$$ $$B \rightarrow bB, b$$ Now we ...
-1
votes
1answer
38 views

NPDA for $\{w : w \in \{a,b\}^*,n_a(w)\geq n_b(w)+1 \}$

I believe that the following NPDA accepts the language $$\{w : w \in \{a,b\}^*,n_a(w)= n_b(w)+1 \}\,,$$ where $n_a(w)$ represents number of symbol $a$'s in string $w$. Is there a two-state NPDA ...
4
votes
1answer
29 views

Method for Creating Any Unambiguous Grammar?

I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars that Was guaranteed to produce ...
2
votes
2answers
116 views

Can there be two different left most derevations for a grammar?

Suppose there is a CFG with the rules S--> Aa A--> Bb B--> A B--> Epsilon To my best understanding the left most derivation would go like this.. ...
4
votes
1answer
46 views

Techniques to prove a language is not DCFL

I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL. Are there any other techniques that will help me to ...
-1
votes
0answers
11 views

An example of a context-free language [duplicate]

Is the following language produced by a CFG? $L=\{aw^{5} | w\in \{a,b\}^{*}\}$ I believe it's not, but I only sense this. I tried to find a suitable sequence of a's and b's to contradict the pumping ...
0
votes
0answers
23 views

How these languages are context free and regular [duplicate]

I found these statements in my textbook without proof. If L is a Context Free Language over a one symbol alphabet then L is regular. Is there no context free language on one symbol ...
1
vote
1answer
34 views

Closure properties between 2 languages of different types [duplicate]

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
0
votes
1answer
32 views

Are regular grammars always LR(1)

The question is fairly straight forward. I just found a question on the internet that asks whether all regular grammars are LL(1) LR(1) I guess they can't be LL(1) because of left recursion, but ...
1
vote
1answer
83 views

Relaxation of the null production restriction in Regular and Context Free Grammars

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of ...
0
votes
0answers
17 views

non-regular context free language with logarithmic stack usage [duplicate]

Can you suggest a context-free language $L$, which is: non-regular has a PDA which accepts all $w\in L$ and uses maximum stack space of $\log(|w|)$.
1
vote
1answer
48 views

Can we build a Nondet. decider PDA using two PDAs accepting $L$ and $L^c$

The title pretty much says everything. When talking about turing machines, it can be easily shown that starting from two Machines accepting $L$ and it's complement, one can build a machine which can ...
0
votes
1answer
55 views

closure property on languages

The above image, taken from planetmath.org, describes the closure property on REG (regular), DCFL (deterministic context-free), CFL (context-free), CSL (context-sensitive), RC (recursive), RE ...
-2
votes
1answer
26 views

Decision Problems of Regular languages and CFL's [closed]

Consider the following decidability questions ...
4
votes
1answer
69 views

Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?

The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$). For example, $L=\{a^nb^n\mid ...
0
votes
1answer
33 views

Create cfg and npda/pda for Language {ww}

I've been trying to make a CFG, and npda/pda for this language (to construct an npda for accepting the language): L(M)={ww:w∈{a,b}∗,|w| is even}. i had already solved the reverse of the language ...
-1
votes
1answer
46 views

Create CFG and pushdown automaton for {ww} [duplicate]

I've been trying to make a CFG, a pushdown automaton and a regular expression for the language $\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$. I understand how the reverse of the ...
0
votes
1answer
40 views

How to make a Post Machine for $a^nb^n$?

I have tried to make a post machine for that all words of the form $a^nb^n$ by the following steps. add a marker '#' read first 'a' read next 'a's and add them read first 'b' read next 'b's and add ...
0
votes
1answer
44 views

What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$ [duplicate]

I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers. Also, in general, are there any good methods ...
-1
votes
2answers
83 views

Pushdown Automata: CFG to PDA

I have the following grammar for a context-free language: $G = (\{S,A,B\}, \{x,y,z\}, P, S)$ with $P = \{S \rightarrow A, A \rightarrow xAz, A \rightarrow xBz, B \rightarrow y\}$ My question is: How ...
1
vote
0answers
103 views

Is the complement of this language Context-Free $\{(a^nb^n)^m \mid n>0,m>0\}$?

I've been asked to decide whether a given language is a Context-Free Language (CFL). If yes, I should find the grammar that creates her, and if not, I need to prove it (with the pumping lemma). The ...
0
votes
0answers
14 views

Why $L=\{Wa^nb^mW^R\mid\:W\in\{a,b\}^+,n>m,m>0\:\}$ is context free? [duplicate]

Please help me, why the following language is context free? $L=\{Wa^nb^mW^R\mid\:W\in\{a,b\}^+,n>m,m>0\:\}$
0
votes
2answers
42 views

what is the best way to approach the construction of nondeterministic PDA's?

I'm trying to construct a PDA for $L = \{w0^i1^j \mid w\text{ ends in } 01 \wedge 2i=3j\}$. My understanding is that I have to first accept an arbitrary number of zeros and ones and then ...
4
votes
0answers
63 views

context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, $$\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}$$ ...
0
votes
1answer
29 views

If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$

I was studying closure properties of CFLs and I came across this. I want to understand why $L^*$ is not a CFL, can anyone explain me in depth with simple examples?
-1
votes
1answer
37 views

Proving that the set of non-universal CFGs is not in NP

How do I prove that $\overline{\mathrm{ALL_{CFG}}}$ does not fall in NP, where $\qquad\mathrm{ALL_{CFG}} = \{\langle G \rangle \mid G \text{ is a CFG}, L(G) = \Sigma^* \}$
1
vote
2answers
47 views

How can this grammar parse such an input?

I've an example which I simply don't get at all. Implement an attributed grammar that checks that either the word ends in $b$ or each prefix of the word contains at least as many $b$s ...
2
votes
1answer
85 views

Language of binary strings divisible by 7

There was a question something like, "Consider the language of all integers converted to binary form. The language of all strings divisible by 7 is : 1) Recognizable by a finite-automaton. 2) ...
0
votes
1answer
26 views

Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$ [closed]

Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$. I just wanted to check if my grammar is correct or not. $$A ...
1
vote
2answers
91 views

PDA recognising all strings with a $1$ in the second half

My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says: Let $\Sigma = \{0,1\}$ ...
3
votes
2answers
76 views

Decide if this language is context free

I got this question for homework: Decide if this language is context free or not: $\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$. Intuitively I think it's not ...
4
votes
1answer
52 views

Do an ambiguous grammar and its corresponding unambiguous version generate the same language?

If I have an ambiguous grammar G and its disambiguated version D. Then which one is true L(D) ⊂ L(G) , L(G) ⊂ L(D) or L(G)=L(D)? As I tried with some examples to transform a grammar to it ...
6
votes
1answer
258 views

Parikh's Theorem: CFL's “contain” regular languages?

The first sentence of the Wikipedia article for Parikh's Theorem states: "Parikh's theorem in theoretical computer science says that if one looks only at the relative number of occurrences of ...
0
votes
1answer
35 views

Help me find the ambiguity in this grammar

I've been sitting on this for 20+ minutes and can't seem to generate a string that is ambiguous. Can anyone help me? The grammar is: $$S \xrightarrow{} SS \mid T$$ $$T \xrightarrow{} aTb \mid ab $$ ...
2
votes
2answers
51 views

Context-free grammars and priority

This grammar is supposed to give priority to multiplication: E -> E + T | T. T -> T * F | F. F -> x. A derivation for "x + x * x" would be (unless I'm wrong): E => E + T => T + T => F + T => x + ...
0
votes
1answer
85 views

Is Myhill-Nerode equivalence class of a language which contains all palindrome pairwise distinct?

In my formal language class, we define a language called PAL, which is on a alphabet set $\Sigma = \{0,1\}$. $PAL = \{w \in \{0,1\}^* : w = w^R\}$. We have proved that every string in this language ...
3
votes
2answers
93 views

Can every context free language written as a intersection of another context free language and a regular language?

I'm preparing an Formal language exam, One question from previous year's final is: Prove or disprove:If L is a context free language, then there exists a language P that is generated by a pure ...
1
vote
1answer
144 views

Reducing context-free languages with polynomial-time reductions

So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$. Can $L \le_p M$ ? Why or why not? How do polynomial time reductions ...
0
votes
1answer
28 views

Is a grammar that accepts function declarations, function calls and expressions (at any order!) necessarily cyclic?

As the title suggests, assume a grammar which has to recognize function declarations, function calls, and expressions, at any order. Does that mean it has to be cyclic, and therefore ambiguous? I ...
3
votes
3answers
252 views

How to represent whitespace in a context-free grammar?

Say we want to support: xx The following grammar does accept it: S -> xAx A -> ε. because S => xAx => xx. But what about supporting: x x I realize this might be a stupid question but I'm ...
0
votes
0answers
45 views

Can we say we reduced a rule if we reduced an equivalent set of smaller rules?

I have constructed an SLR(1) parsing table with the following rules. S -> S + S + S (rule 1) S -> S + S (rule 2) S -> y Is reducing rule 2, then shifting + and y, then again rule 2, equivalent ...
-3
votes
1answer
28 views

Eliminating Null Productions from Context Free Grammar

Here is a problem I am trying to solve: S -> 0A0 | 1B1 | BB A -> C B -> S | A C -> S | e I know that C is nullable (since it produces an epsilon) and ...
4
votes
2answers
79 views

Prove or disprove: L^2 context free implies L is context free

Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language L. I was trying to prove that L^2 is context free which ...