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

learn more… | top users | synonyms

-3
votes
0answers
27 views

intersection of regular and context free languages [on hold]

how to prove that the intersection of a context free language and a regular language is always context free? I want simple example of this to make it clear for myself..
2
votes
2answers
25 views

Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable?

Suppose I have a set of strings $S$ that is generated from the alphabet. Suppose I have a DFA $D$ and a CFG $G$, are the questions of $\{D\mid D\text{ is a DFA and }L(D) = S\}$ and $\{G\mid G\text{ ...
0
votes
1answer
38 views

Confusing example of a language which may be Context-free or not context-free

Hi so consider the language $L= \{(0^i)(1^j)\mid i=k*j \text{ for some positive }k\}$ Could I not rewrite this as $\{((0^k)^j)(b^j)\mid k>1\}$. Seeing it in this form makes me think of a form $a^n ...
2
votes
2answers
36 views

Ambiguous context free

Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.
3
votes
1answer
44 views

A non-regular language satisfying the pumping lemma

I got a problem to solve, which is to demostrate that the language $L$, given by: $L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$ Satisfies the pumping lemma. Is not ...
1
vote
1answer
33 views

Prove that this language is not context-free [duplicate]

I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether ...
0
votes
0answers
39 views

The pumping lemma for the context free languages [duplicate]

I am trying to use the pumping lemma to show this is not a context free language $$ L = \{a^n b^{2n} a^n\mid n\ge 0\} $$ My idea is fist assume it is a CFG language and let $n$ be the pumping lemma ...
1
vote
0answers
15 views

Are deterministic context-free languages closed under reversal of languages? [duplicate]

It is well known that context-free languages are closed under the reversal of $L$. My answer to the question "Is the time reversal symmetry of non-deterministic computations important?" notices that ...
1
vote
0answers
23 views

Is $\{u\#v \mid u\not=v\}$ context-free? [duplicate]

Is the following language context-free? $$ \{u\#v\in\Sigma^* \mid u\not=v \text{ and } u,v\in\{0,1\}^*\} $$ You can assume $\{0,1,\#\}\subseteq\Sigma$. Unnecessary background information: I am ...
-1
votes
1answer
40 views

How to find the Context-free grammars for this language [duplicate]

give a context-free grammar describing the language L={w∈{a,b}∗∣w is of the form xby, where |x|>|y|}. I had one solution like this ...
1
vote
1answer
61 views

CFGs: detecting infinitely many derivations of a single string

Some particularly degenerate CFGs can produce a single string in infinitely many ways: for a dumb example, $S \to SS \mid \epsilon$ can produce the empty string as $S \to \epsilon$ or $S \to SS \to S ...
0
votes
0answers
15 views

CFG for language [duplicate]

I'm trying to create CFG for a language. The language is following: {w | {a,b}* | w should have one more a than there are b: s } I built following grammar: S -> aB | aSb | bSa | abS | baS | Sab | ...
0
votes
0answers
37 views

LL(1) grammar for the untyped lambda-calculus

What I want to do I am trying to define a LL(1) grammar of the lambda-calculus. What I did Here is the grammar: $Term \to Abs$ $Term \to App$ $Abs \to \lambda \ id \ . \ Term$ $App \to Var \ ...
0
votes
1answer
26 views

Is this grammar LR(1)?

A bit confused about whether this grammar is ambiguous or not C' -> C C -> d C u C C -> d C C -> ε I tried building the DFA for this but I get this ...
1
vote
1answer
44 views

Proving that any CF language over a 1 letter alphabet is regular

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far: Let L be a ...
0
votes
0answers
32 views

A context free grammar for the language of even-length non-palindromes [duplicate]

I am trying to find a context free grammar for the language $L = \{xy \mid |x|=|y| \text{ and } x≠y^R\}$ where $y^R$ is the reverse of string y and $x, y\in \{a,b\}^*$ . Here is a possible ...
3
votes
1answer
96 views

Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an ...
1
vote
1answer
46 views

What is the complement of ACFG

What is the complement of $\mathrm{ACFG} = \{ G \mid G \text{ is a CFG and }L(G) = \Sigma^* \}$? I think it is $\mathrm{ECFG} = \{ G \mid G\text{ is a CFG and }L(G) = \emptyset \}$. It makes sense ...
1
vote
0answers
63 views

Converting Chomsky Normal Forms to Greibach Normal Form

Here is a passage from Kozen's Automata and Computability (pages 145-146) that I'm confused about: Now we show how to convert an arbitrary grammar to an equivalent one (except possibly for $ ...
1
vote
1answer
60 views

How can I quickly guess if L is context-free or det. context-free?

I have a language, for example $\{a^m b^n c^n \mid m, n \in \mathbb{N}, m = 2n\}$ $\{a^l b^m \mid l, m \in \mathbb{N}, l=4^m\}$ How can I see at a glance whether the language is deterministic ...
0
votes
0answers
16 views

Pumping Lemma for CFG - How to do it? [duplicate]

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
39 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
77 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 ...
0
votes
2answers
73 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
38 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
30 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
49 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
33 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
122 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
61 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 ...
0
votes
0answers
24 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
35 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
33 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
86 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
56 views

Can we build a nondeterministic decider PDA using two PDAs accepting a language and its complement?

When talking about turing machines, it can be easily shown that starting from two machines accepting $L$ and its complement $L^c$, one can build a machine which can fully decide if a word is inside ...
0
votes
1answer
65 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 ...
4
votes
1answer
70 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
56 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
61 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
2answers
58 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
50 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
109 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
119 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
46 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
92 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?