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
22 views

How can I extend a context-free grammar to Lexical semantics?

Here it was suggested that I may need Lexical semantics for my parsing problems. How can I extend a context-free grammar to Lexical semantics? I've thought attribute grammars already, but they seem ...
2
votes
1answer
29 views

CFG for words that are not a concatenation of the same word [duplicate]

I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language: $ L = \{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ...
-1
votes
0answers
27 views

Greibach Normal Form problem

I have this grammar: $S \to AA \mid 0$ $A \to SS \mid 1$ At first there is no left-recursion. So, I go forward to enumerate non-terminals. I get $S=A_1, A=A_2, 0=A_3, 1=A_4$, so $A_1 \to A_2A_2 ...
0
votes
1answer
37 views

Grammar ambiguous or not?

So I've been struggling for the past hour with $G=(\{S\},\{a,b\},P,S)$ with productions $S\to aaSb | abSbS | \varepsilon$. I need to prove whether this grammar is ambiguous or not. Thus far I think it ...
3
votes
1answer
58 views

Is no language with the non-primes property context-free?

A language $L$ is said to have the "no primes" property if: For every prime $p$ there are no words $w$ in $L$ s.t. $|w|=p$. For every non-prime $m$ there is at least one word $w\in L$ of length ...
3
votes
2answers
50 views

Is it decidable whether a given context free grammar generates an infinite number of strings?

Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
1
vote
2answers
91 views

Does the language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$?

Does the Context Free Language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$? Does $t$ fix $n$? I think the string belongs to this language.
3
votes
1answer
125 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
1
vote
1answer
48 views

Language of words that begin and end with same symbol and have equal numbers of a's and b's

I wish to find the CFG for a language on two symbols (say a and b) whose words begin and terminate with the same symbol, and have equal quantities of a's and b's. What is the thought process I should ...
1
vote
2answers
28 views

Techniques to create a PDA for a language that is the conjunction of two languages

When I was working with finite automata, I figured out that we can put together two FA two build a new one that is the intersection between the two. This is possible because regular languages are ...
3
votes
0answers
49 views

Proof $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic

Without using pumping lemma for deterministic context-free languages I need to prove that the language $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic. Someone ...
0
votes
1answer
63 views

DPDA for $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ according to empty stack criterion

I'm having some trouble with the following language: $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ with alphabet $A=\{0,1,2,3\}$ I'd like to find a deterministic pushdown automata to recognise it ...
-1
votes
0answers
43 views

How to solve a left-recursive Problem in grammar

I have a grammar like this and it has different type of problems 1) X -->YX|$ 2) Y --> ε|A|let A in Y|let A in E end 3) A--> x=E 4) E-->(E)|E*E|*E|EE|x|ƛx.E I tried to solve that and this my ...
-1
votes
0answers
45 views

How to prove the following language is not context-free? [duplicate]

I'm having trouble to get the whole point of the pumping lemma for CFL and how to write the proof correctly. I'll be happy to get some help to prove the following language is not a context-free: ...
0
votes
1answer
47 views

Trouble understanding how to create a grammar parse tree

I'm starting an online Computer Science class called Advanced Programming Languages, and the book asks me to create a parse tree and generate a grammar from it. Here are the exact instructions: ...
0
votes
2answers
70 views

How to convert PDA to CLF

I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG? For example: to write CLF for the automata EDIT: My attempt: $S=A_{03}$ ...
-3
votes
1answer
83 views

Showing that $\mathscr{L}$ is not context-free-grammar language

Let $"t"$ and $"s"$ be a words we will say that two words are "completly different" if for all $1\leq i\leq |t|$ the $i$ letter in $t$ diffrent from the $i$ letter in $s$. Prove that the language ...
3
votes
0answers
36 views

How to prove “if every subset of a set is a CFL, then the set must be regular.”

"If every subset of a set is a CFL, then the set must be regular." I want to prove it, could anyone please give me some hints?
3
votes
1answer
18 views

Deriving from a terminal word in a context free grammar

Just to make it clear. (since my book doesn't mention anything like this) Suppose we have a context free grammar $G=(V,T,P,S)$. where $T=\{a,b\}$ (The other sets doesn't really matter). Since ...
0
votes
2answers
31 views

Are all non-terminals of the CFG given by the LHS of productions?

A definition for terminals and non-terminals of a CFG says that terminals: The symbols that do not appear at the LHS of productions. Therefore, Are all non-terminals of the CFG given by the LHS ...
0
votes
1answer
36 views

Do “symbols” = terminals in CFGs?

Are the "symbols" of a context-free grammar the same thing as the terminals? Are the set of symbols and set of terminals the same?
3
votes
1answer
61 views

Proving that every derivation-tree has at most one leftmost-derivation in a context free grammar

I am trying to prove the following theorem: For every derivation-tree in a context-free grammar $G=(V,T,P,S)$ there exists at most one leftmost derivation. My partial proof by contradiction (I ...
1
vote
1answer
77 views

Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$

With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$ I need to: run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can ...
3
votes
1answer
43 views

Lower bound for number of nonterminals in a CFG

Let's say we have a context-free grammar for the language $a\mbox{*}b\mbox{*}c\mbox{*}$. Is there a way to determine a lower bound for the number of nonterminals in this grammar? I'm pretty sure you ...
1
vote
2answers
107 views

Context free languages belongs to NTIME(n)?

As the question states, how do we prove that for every L ∈ L2 (context-free class of languages) is true that L ∈ NTIME(n)? Can anyone point me to a proof or outline it here? Thanks!
3
votes
1answer
68 views

Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
2
votes
3answers
57 views

Why is the distinction between linear and context-free grammars useful?

The linear grammar is a grammar that's either left, right or left and right linear. The context-free grammar can contain any kind of productions of non-terminals and terminals. All linear grammars ...
0
votes
2answers
89 views

Context-free grammar for“not-at-all” palindromes

I need to bulid a context-free grammar for $\qquad \mathscr{L_4}=\{w\in\{a,b,c\}^* \mid w\text{ is not palindrome at all}\}$ Not palindrom at all: We will say that a word $w$ is not palindrome at ...
-1
votes
1answer
27 views

Unambiguous CFG that generates regular language according to Pumping Lemma?

The pumping lemma for regular languages states: Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can ...
5
votes
1answer
69 views

Show that some context free languages must contain more that one non-terminal

Context free languages that has only one non-terminal is a proper subset of context free languages and they does not contains regular set. Since, CFL is more powerful than FSM and contains regular ...
-1
votes
1answer
27 views

Tools or techniques for studying the language a CFG produces? [duplicate]

When developing a CFG, I find that one can be confused about whether the grammar is correct, i.e. whether it recognizes only the required strings and not other strings. But this can be hard to see? ...
0
votes
1answer
19 views

How to convert improper CFG to weakly equivalent one?

In wikipedia there's the definition for "Proper CFG". A context-free grammar is said to be proper, if it has $$\text{no unreachable symbols}: \forall N \in V: \exists \alpha,\beta > \in ...
-2
votes
1answer
35 views

Can the CFG model Kleene star?

Can the context-free grammar model the Kleene star * operation of regular expressions? I.e. can it express (a|b)* somehow? P -> aPP -> bP ? But when would this terminate?
-2
votes
1answer
42 views

All regular languages are context-free so why does the terminology not reflect that? [closed]

Since Regular languages $\subset$ Context-free languages, then Regular languages are Context-free languages? Why is the terminology so different then? To me these seem like a totally different class ...
0
votes
1answer
40 views

Where can I find a reasonable NLP CFG or CSG for English?

I'm looking to do natural language parsing and looking for how the CFG (or CSG) should be defined for English. Surely one'd expect to find one from the internet already, but do you know where? It ...
0
votes
3answers
77 views

Proving/Disproving that language L is non-regular/CFL

Here are three examples of questions I run into. I'm not looking for solutions. If $L$ is CFL then $L' = \{ ww^R | w \in L \}$ is non-regular. If $L$ is non-regular then $L' = \{ ww^R | w \in ...
5
votes
1answer
51 views

Algorithm to find a minimal regular language containing given context-free language

I am not sure that the problem is in general solvable, but here's an example of what I mean: Any context-free language has a trivial regular language that contains it: $\Sigma^*$. The language ...
-1
votes
1answer
20 views

Context-free grammar for “member of”/set membership?

I'm wondering whether context-free grammars (or what else) can be used to implement "member of" structures, which are structures for describing that something is a member of something. E.g. I want to ...
1
vote
0answers
32 views

Parsing based on logical connectives and quantifiers?

What techniques exist for parsing sentences based on logical connectives and quantifiers? That is, for parsing sentences that are structured "around" logical connectives and quantifiers. E.g. [A] ...
0
votes
1answer
39 views

What exactly is the LL(k) grammar condition?

I have a bit of trouble understanding the definition of LL(k) grammars. Here it's defined as: for every pair of production rules $A\rightarrow α$ and $A \rightarrow β$ the following ...
1
vote
0answers
42 views

Use the pumping lemma to prove that {www} is not context-free

Use the pumping lemma to prove that the following language is not context-free. $\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$ I am studying for an exam and really trying to understand this question. ...
0
votes
1answer
36 views

Show Language is not context free without pumping lemma [duplicate]

Can we show that following language is not context free using Push down automata approach? L = {a^i b^i a^i : i>=1} For every a we will Push 'A' onto stack, ...
-1
votes
1answer
63 views

Language of Palindrome-Prefixed Words

Classify the language $L = \{xx^Rw\ \big|\ (|x| \geq 0\ \wedge |w|\gt 0)\ where\ x,w\in\Sigma^*\}$ as one of: Regular but not Context-Free Context-Free but not Regular Decidable ...
3
votes
3answers
125 views

Is the language $a^i b^j c^k$ with $i+j > k$ context-free?

I am learning about Context Free Grammars and currently stuck on the following question. Is the following language context-free? If not, then how can we prove it using Pumping Lemma? $\qquad ...
4
votes
2answers
127 views

Pumping lemma: if you can keep pumping, what does this tell you?

Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this ...
-1
votes
0answers
46 views

Devise a context-free grammar G that generates the language E = {x ∈ {0, 1}* | x has the same number of 0’s as 1’s}

I have this assignment that I'm not really comfortable about so I would like any feedback toward my thinking below the questions: a. Devise a context-free grammar G that generates the language: ...
4
votes
2answers
141 views

Figuring out the language of a non-linear CFG

I have the CFG G with the following production rules: $$ S \to aSaS \mid b $$ Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, ...
1
vote
1answer
56 views

Show that the following construction is not a correct proof for Context Free Grammars

Give a counterexample to show that the following constructions are not correct proofs for the star operation: Given a CFG $G = (V,Σ,R,S)$, add the new rule i) $ S → SS$ or ii) $S → SS|ε$. ...
0
votes
1answer
33 views

Why is this language not context free?

I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not ...
0
votes
1answer
40 views

How to check if my language is context-free can't seem to solve it using pumping lemma

I have a language and I am trying to see if it's context-free or not, by trying to use a pumping-lemma but I can't figure it out, been reading a lot of other posts but still struggling to apply it to ...