Questions tagged [context-free]

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

203 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
30 views

How to generate a context-free grammar that defines a regex expression

As the title says, I have been asked to generate a grammar that defines the language of regular expressions. The symbols are: + . * | ? char I tried and came up with this but it doesn't work when ...
1
vote
0answers
52 views

A Formal Grammar: defining English counting numbers?

I would like to define a grammar that produces and recognizes the counting numbers of the English language. I created the production rules below based on the assumption this is context-free, but I am ...
1
vote
1answer
769 views

How to convert regular expression to CFG?

How can I convert the regular expression (ab*)*b to a context-free grammar? When I look for examples I keep seeing plus signs in the expression but I don’t have any. Is that just a different way of ...
1
vote
0answers
48 views

How to interpret this context free language?

$S \to aAA$ $A \to aS \mid bS \mid a$ Trivial thing: starting and ending with a Atleast 3 a's are definitely present (These are very layman observations...but seriously I am unable to figure out what ...
1
vote
0answers
24 views

CFG to CNF, but stuck on the last few steps

I recently learned about the conversion, but I seem to be stuck. I need to convert the following CFG to CNF: $S → XY$ $X → abb|aXb|e$ $Y → c|cY$ There is no S on the right side, so I did not need ...
1
vote
0answers
227 views

Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?

My textbook states: Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in general—a CFG in Chomsky normal form may or may not be ambiguous, just like we have for ...
1
vote
0answers
551 views

Empty string in language with grammar in Chomsky normal form

In their book, Ullman et al says: Every nonempty CFL without $\epsilon$ has a grammar $G$ in which all productions are in one of two simple forms, either: $A\rightarrow BC$, where $A,B$ and ...
1
vote
0answers
44 views

Deciding whether CFG generates the empty word

Give an algorithm to decide the following problem: given a CFG $G$, does $G\Rightarrow^\star \epsilon$? That is, given a grammar can it generate the empty word? How can I make sure my algorithm is ...
1
vote
0answers
133 views

Is ASM a regular language?

I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world ...
1
vote
0answers
69 views

Context-free or not: $a^nww^Ra^n$

Is the following a context-free language? $$L = \{a^n w w^R a^n \mid n \geq 0, w \in \{a,b\}^*\}$$ I think no because the number of $w$'s is not equal. Somebody please guide me.
1
vote
0answers
60 views

Prove that grammar $S \to aSc | \epsilon | bBc$ ,$B \to bBc | \epsilon$ generates language $\{a^ib^jc^{i+j} | i,j \ge 0 \}$

Prove that grammar $G$ with productions: $S \to aSc|\epsilon | bBc$ $B\to bBc | \epsilon$ Generates language $ L = \{a^ib^jc^{(i+j)}$ | $i,j \ge 0 \} $ Step 1. Prove $L(G) \subseteq L$ . We are ...
1
vote
0answers
29 views

Using DPDA instead of LR parsers

If LR parsers handle only DCFLs than why we don't just use dpda to parse these languages? What are advantages of using LR parsers over DPDA? Is it that it is easy to built autonomously or something ...
1
vote
0answers
37 views

CYK algorithm - how to handle unknown terminals given in a sentence to parse?

There is a given treebank which we derive the Probabilistic context free grammar. I wonder how do one handles with a given sentence which includes terminals that don't exist in the derived rules? Is ...
1
vote
1answer
81 views

Acceptance problem for CFGs is not regular

Let $ACFG$ be the language of all encodings $(C,x)$ where $C$ is a context free grammar that generates a language containing $x$, i.e. $ACFG$ is the acceptance problem for context free grammars. It ...
1
vote
0answers
99 views

Accounting for spaces in grammars

Sometimes in a context free language we'd like to require spaces between productions, and sometimes not. For example take the following part from a grammar describing grammars: ...
1
vote
0answers
167 views

How to generate random strings from Context-Free Grammar in GNF

I need to generate random strings given a grammar in Greibach Normal Form. The naive approach would be to generate a random integer n and perform ...
1
vote
1answer
81 views

SLR(1) Table construction, FIRST and FOLLOWS

when constructing the SLR(1) table for some grammar I need to compute the FOLLOW set for all terminals in order to decide where and when to reduce. Do I compute theme for the augmented grammar or ...
1
vote
0answers
154 views

Do SLR(1) parsers have lookahead?

The SLR(1) parses AFAIK does not have any lookahead with it then why do we write it as SLR(1) and not as SLR(0). The thing about parsers which I read online taught me that if it's LR(K) then K ...
1
vote
3answers
189 views

Need help understanding what co-recursively enumerable means

Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
1
vote
0answers
84 views

Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable

I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that ...
1
vote
0answers
467 views

How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.(\| is the escape character, since | is a special character in grammar's pattern). ...
1
vote
0answers
457 views

Proving a language is not context-free using the pumping lemma

I had a question regarding the use of the pumping lemma for a particular language I came across. I feel like I have almost solved it, but have gotten stuck on the last steps and wanted some advice. ...
1
vote
0answers
141 views

Is star closure of reverse of grammar equivalent to reverse of closure of that grammar

I need to proof if that it's true or not. $ (G^R)^* = (G^*)^R $ If $G$ is a CFG and $ G = \langle V, \Sigma, \delta, S \rangle $ where $ V $ = Set of Variables or Non-Terminal Symbols $ \Sigma $ = ...
1
vote
0answers
75 views

Constructing Context Free Grammar with 3 terminal symbols, with two dependent pairs

I am new to Context Free Grammars and am having trouble wrapping my head around how to approach writing a CFG for the following language: ...
1
vote
0answers
427 views

How do we evaluate semantic actions in L attributed SDT?

I came across following problem: $S→ER$ $R→∗E\{print(′∗′);\}R∣ε$ $E→F+E\{print(′+′);\}∣F$ $F→(S)∣id\{print(id.value);\}$ Here $id$ is a token that represents an integer and $id.value$ ...
1
vote
0answers
156 views

Is universality problem of single state NPDA decidable?

I came across following problem: Given single state non deterministic pushdown automata $M$, whether $L(M)=\Sigma^*$ is decidable? Now I know for DPDA/DCFG/DCFL, universality problem is ...
1
vote
0answers
583 views

Converting a non-deterministic context free grammar to deterministic

I have the non-deterministic context free grammar $$I \to abcX | abdY$$ $$X \to X d | \epsilon$$ $$Y \to XX |I$$ and i want to convert it into a deterministic. I know that the rules $I \to abcX | abdY$...
1
vote
3answers
1k views

Context-free grammar for binary words

I am supposed to create CFG for this languague: $L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$ where $|w_b|$ is count of terminals $b$ in $w$. For example: aa - OK, no 'b' abb - wrong, only ...
1
vote
0answers
61 views

Pumping lemma for CFL language

Let $L$={ $\alpha$ in {$a,b$}* | $\alpha$ has exactly two symbols b } .Prove that $L'$ = { $\alpha^n$ | $\alpha$ in $L$ ,$n \ge$0} is not context-free.I was thinking to prove it that way: Since $a^nba^...
1
vote
0answers
86 views

Where is left recursion in this little CF grammar?

S → D D → E | EC E → anyId C → B | .D | B.D B → <S> | <SA> A → ,S | ,SA The tool I am using keeps complaining about left recursion in this grammar. I ...
1
vote
0answers
406 views

How to draw NPDA for language $L = \{ a^i b^j c^m \mid m \ge \min( i,j) \} $

$L_1 = \{ a^i b^j c^m \mid m ≥ min(i,j) \}$ $L_2 = \{ a^i b^j c^m \mid m ≥ max(i,j) \}$ Which language is CFL ? ANS : $L_1$ is CFL but $L_2$ is NOT. My understanding :  For Language $L_1$ : ( ...
1
vote
0answers
134 views

Complexity of emptiness checking for visibly pushdown automata?

Visibly pushdown automata [1] are pushdown automata in which input symbol determines whether push or pop operation happens in the stack. Does anyone aware of tight lower bound for their emptiness ...
1
vote
0answers
221 views

Proving that a language cannot be generated by linear grammar

We were said at school that the language $L$ over an alphabet $\sum = \{a,b\}$ where the number of $a$'s is twice the number of $b$'s, formally $L = \{ w \in \{a,b\}^* \mid |w|_a = 2|w|_b \}$ cannot ...
1
vote
0answers
50 views

reusable expressions in Context free grammars

say, we add the option of allowing let expressions to context free grammars: let defines a variable that defines an expression ...
1
vote
0answers
313 views

Given a context free grammar, prove if the grammar is ambiguous

Here is a context free grammar that I have been given for practice: Grammar $G = (V,\Sigma,R,S)$ where $V$ is $\{S,A,B,a,b,c\}$ and $\Sigma$ is $\{a,b,c\}$. $R$ has the following rules: $$\begin{...
1
vote
0answers
167 views

Context Free Grammar Prove Un-/Ambiguity

I know, it is not possible to decide whether a context free grammar is ambiguous or not. However, I am having a really hard time preparing for an upcoming exam in which I'll have to give a prove of un-...
1
vote
0answers
200 views

Given a DFA $A$ and a CFG $G$, decide whether $L(G) ⊆ L(A)$

Propose a reasonably efficient algorithm to decide, given a DFA $A$ and a CFG $G$, whether $L(G) ⊆ L(A)$. I think that I have to prove it by computing the intersection of both (DFA,CFG), and then ...
1
vote
0answers
99 views

How can we avoid mistake in LL(1) parse tree?

I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...
1
vote
0answers
65 views

Decidability Proof of $A_{Cfg}$

I am a beginner to complexity theory and I came up with the following proof of decidability of $A_{Cfg}$ = {$<G,w>|G$ is a context free grammar that generates string $w$} The Turing machine ...
1
vote
0answers
44 views

Modifying the grammar to include another operator

I have this grammar for arithmetic expressions E -> E+T | T T -> T X F | F (X is cross product operator) F -> (E) | a Now I am wanting to add the exponential operator ^ to it, it needs to ...
1
vote
0answers
77 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] ...
1
vote
0answers
41 views

Am I allowed to remove left recursion like this?

I have: <A> -> <B> <C> <D> <D> -> <D> <C> <D> -> lambda Since ...
1
vote
0answers
104 views

Dangling else determinism

The natural grammar for dangling "else" is ambiguous. But there exists an unambiguous version of the grammar that links the "else" to last uncompleted "if" statement. Is this version also ...
1
vote
0answers
41 views

Language involving length constraints and reversal

Why is the language $A=\{wtw^r: w,t\in\{0,1\}^*\text{ and }|w|=|t|\}$ not a context free language? It is turning out to be really tricky. Is there an easy way to show this?
1
vote
0answers
24 views

How equality of item (production state) is defined in LR parser?

Whenever I read about equality I took it for granted, but few days ago I wondered if my understanding is not too shallow. Consider such example (taken from: http://david.tribble.com/text/honalee.html):...
1
vote
0answers
601 views

Are DCFLs closed under concatenation with a regular language?

I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to ...
1
vote
0answers
518 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 \ ...
1
vote
0answers
530 views

LL(1) grammar for postfix ternary operations

Suppose the task is to make an LL(1) grammar for postfix operations, where the only operation is ternary. Obvious approach is $N$ - number $O$ - operation $S$ - expression rules:...
1
vote
0answers
52 views

Is this theorem about left-factored grammars correct?

I am working on CFG grammars, LL grammars in particular and I encountered the following theorem in the slides of presentations written by my professor: A CFG grammar cannot be left-factored if all ...
1
vote
0answers
115 views

Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?

I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related. Suppose I have a regular expression: RE=(aa)?(aa) and I convert it to a grammar: G ::= A B A ::= C | (...