Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [context-free]

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

1
vote
1answer
33 views

Is this context-free grammar correct for this regular expression?

I have created a context-free grammar $$ \begin{align*} &S \to S_1 \mid S_2 \\ &S_1 \to aS_3bS_4 \mid \epsilon \\ &S_2 \to bS_4 \\ &S_3 \to aS_3 \mid \epsilon \\ &S_4 \to aS_4 \...
2
votes
2answers
36 views

Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$

How can I prove that $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$ is decidable ? I know that $EQ_{CFG} = \{⟨G, H⟩ \mid \text{$G,H$ are CFGs and $L(G) = L(H)$}\}$ is not.
1
vote
1answer
29 views

is $0^x1^y$ context-free?

given that L is regular, does the following make a context-free language?: i) $\{0^x1^y \mid 0^{x+y} \in L\}$ ii) $\{0^x1^y \mid 0^{x-y} \in L\}$ since L is regular, i presumed that i) can be put ...
2
votes
0answers
30 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
1
vote
2answers
36 views

What's the right way to think about a CFG symbol with an infinite null derivation?

I'm curious about the right way to characterize symbol $A$ in a CFG like this one: $$ \begin{align*} A &\to A B\\ A &\to x\\ B &\to y\\ B &\to \varepsilon \end{align*} $$ $B$ is ...
1
vote
1answer
14 views

If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
0
votes
1answer
20 views

Give a Context Free Language, is the complement of this language always recursive(REC)?

I have seen some people make an argument that given the fact that Context Free Languages are proper subset of REC which is closed under complementation thus complement of a CFL must be in REC. I ...
-1
votes
2answers
33 views

How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]

i am trying to find a cfg for this cfl L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$ is there a way to count the number of 0's or 1's in the string?
0
votes
0answers
28 views

Get grammar from his LALR(1) parsing table

I have a problem with this exercise. This is the LALR(1) parsing table for the grammar G. How can i get the productions of G? Thanks :)
0
votes
1answer
17 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
1answer
33 views

Is the following Grammar LL(1)

I was given the following grammar $S \rightarrow S ( S ) S\mid \epsilon$ First I was asked to eliminate left recursion, yielding me the following : $S \rightarrow S' $ $S' \rightarrow (S)...
0
votes
0answers
19 views

Are there any formal grammars describing the set of all directed graphs?

Let GRAPHS be the set of all directed graphs. Is there a set of strings STRYNGS such that there exists a bijection ...
1
vote
1answer
37 views

Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars?

Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY. We want an algorithm which accepts GX and Gy as inputs. The algorithm will ...
1
vote
1answer
16 views

Can Non-Linear Grammars generate Regular Language?

I stumbled upon the following non-linear grammar $$S \to AB$$ $$A\to aaA\mid \epsilon$$ $$B \to Bb\mid \epsilon$$ and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} ...
-1
votes
0answers
22 views
0
votes
0answers
20 views

How a regular language , context free language and context sensitive grammar are used in compilers to shape up the languge? [duplicate]

I know that regular language can be used for pattern matching , context free language is used for syntax matching and context sensitive for semantic or meaning of the sentence . But i have found it ...
-1
votes
1answer
32 views

Verify this cfg is finite or not

S-> aAb | aBd A-> ab | Bd | e B-> ab | d | f I am getting a loop during CNF conversion but in question it stated that it's a finite language.
1
vote
1answer
87 views

Can Deterministic Context free Grammars be ambiguous?

I know that DCFL are unambiguous languages and DCFL languages have one-to-one correspondence with LR grammars. But I wanted to know if there can be an instance that deterministic context free grammar ...
2
votes
1answer
41 views

How to make an unambigous grammar of a programming language

We know that the decision problem of whether an arbitrary context-free grammar is ambiguous is undecidable. My question is how are made the unambigous grammar of programming language? My guessing is ...
1
vote
0answers
32 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 ...
0
votes
1answer
45 views

Is the language $(a^n)^mb^n$ context free?

$(a^n)^mb^n$ for $m,n\ge 1$ This can be rewritten as $a^{nm}b^n $ i.e. number of $a$'s is a multiple of number of $b$'s, or for every m $a$'s there is one $b$. I thnk this language can be accepted ...
0
votes
0answers
19 views

How to find follow sets in this question?

E -> TE’ E’ -> +T E’|Є T -> F T’ T’ -> *F T’ | Є F -> (E) | id How to compute Follow(E),Follow(T),Follow(T’),Follow(E') and Follow(F)?
2
votes
1answer
156 views

Prove that every CFL is decidable in O(n) space

this question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was: Prove that every context free language $A$ is in $\mathrm{SPACE}...
0
votes
0answers
16 views

Converting context-free grammar to chomsky normal form and ait greibach normal form [closed]

I am sorry , my English is not good. My question is: S->aAc|aSc A->aAb|ab I found this as CNF: S0->DB|DC S->DB|DC A->DF|DH B->AN C->AN D->a F->b H->AF N->c İs this correct answer for CNF ? I am ...
1
vote
1answer
28 views

Are there strings which get accepted only by PDA by empty stack and not by PDA by final state, and vice versa?

Can the same PDA accept both by final state and empty stack in the sense that there are some set of strings that are getting accepted by empty stack, while other set of string by final state and ...
2
votes
0answers
39 views

What strategies exist for handling/resolving ambiguity in parsers?

I define a parser as a context-free grammar with semantic actions for each production. It is not defined in what order the semantic actions run, just that the semantic actions of the non-terminals in ...
1
vote
1answer
28 views

Fitting a regular grammar to strings from a PCFG: how big does it get?

Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$. For finite $n$, it is always possible to find a regular ...
0
votes
1answer
18 views

Given set of grammar rules, how to find if they correspond to Context-free or unrestricted

Given set of grammar rules, how to find if they correspond to Context-free or unrestricted? Just for Understanding (don't solve the below one), eg: \begin{align} S &\rightarrow B/A, \\ 1B &\...
2
votes
1answer
51 views

How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount

I know that CFG for $$ \{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is $$ S\rightarrow ab/abb/aSb/aSbb $$ but I am not able to tweak it in such a way that it is strictly in between m and 2m and not equal to ...
0
votes
1answer
16 views

Construct context-free grammars that generate for the languages L(G) = {01(110)^n 10 (11)^n : n >= 0}

I have given this question as home assignment. I tried a lot to solve it but couldn't found any solution. Please help Thanks in Advance!
1
vote
1answer
38 views

Leo's deterministic reduction for Earley Parsing

I am trying to build an Earley parser using the Wikipedia pesudocode as a base, with Aycock's fix for epsilon rules as follows: ...
0
votes
0answers
19 views

Is the set of context free grammars that generate no words in co-RE? [duplicate]

Is the $\{ \langle G \rangle \mid L(G) = \emptyset \}$ recursively enumerable or co-recursively enumerable?
1
vote
1answer
14 views

Efficiency/Redundancy in Chomsky normal form

I have a context-free grammar with the following production rules, $S$ being the start symbol: $$\begin{align*} S &\to AB \\ A &\to a \\ B &\to a\end{align*}$$ Is this in Chomsky normal ...
0
votes
2answers
41 views

What is an example of a decidable language?

I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?
0
votes
1answer
76 views

How to give a context free grammar for any given language ie: a^n (ba)^m a^n

i am trying to understand Context free grammar and generate a CFG for any given language. when you're given a language , what is the best way to generate a CFG from it? are there any steps to follow ...
0
votes
2answers
109 views

Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

Give a context-free grammar for the following language: $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$ So far, this is the solution that I have been able to come up with, though I am not sure how accurate ...
0
votes
1answer
35 views

Need help understanding what co-recursively enumerable means

Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \sum^{\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
1answer
35 views

Is the set of context free grammars that generate all words in co-RE?

Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.
1
vote
1answer
20 views

Is $L = a^{n}b^{n+m}c^{m} | n,m \geq 0$ a context free or a recursive language?

My initial thought is that L can't be context free since I can use the pumping lemma. I also don't think a grammar can be generated since it needs to keep track of the number of c's and a's. However, ...
0
votes
0answers
25 views

Given a CFL L and a regular language R, is $\overline{L} \cap R = \emptyset$ decidable or undecidable? [duplicate]

I think it is undecidable since context free languages are not closed under complementation. But I'm stuck because if $\overline{L}$ is regular than $R \cap R = \emptyset$ is decidable since every ...
0
votes
2answers
45 views

if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
3
votes
1answer
65 views

Does every infinite context free language contain an infinite regular subset?

Can someone explain to me if this is true or not?
1
vote
1answer
43 views

Is $\{ 0^p1^q0^r \mid p \neq r \}$ context-free?

Consider the following languages: $$ \begin{align*} L_1 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0 \}, \\ L_2 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0, \; p \neq r \}. \end{align*} $$ Which one of ...
1
vote
2answers
108 views

Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
0
votes
0answers
25 views

Building deterministic pushdown automaton for given grammar

I am trying to build a DPDA for the given grammar: $S \to aR$ $R \to bRT \ |\ \varepsilon$ $T \to cSR \ |\ \varepsilon$ I tried simplifying grammar first (removing null and unit productions, ...
1
vote
1answer
35 views

How prefix property of language affects the PDA

I know that every DPDA (deterministic PDA) is a PDA (more specifically, non-deterministic PDA). But I found it hard to understand, not that every DPDA is an NPDA, but some results that contradict this ...
0
votes
1answer
47 views

Prove complement a^nb^nc^n is contextfree

So the complement of L1 = {$a^{n}b^{n}c^{n}$ | n $\geq$ 1} would be L2 = {a,b,c}* \ {$a^{n}b^{n}c^{n}$ | n $\geq$ 1}. In other words, any combinations of a,b and c where we dont have an equal number ...
0
votes
0answers
20 views

Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#…#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]

Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
0
votes
0answers
13 views

contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2} [duplicate]

Is this language contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2}. I think it's not but can't prove it.
0
votes
0answers
27 views

Context free grammar problem with hashtag

I am trying to solve the following context free grammar problem with hashtag approach but i can't figure it out. Can anyone help please? Show a context-free grammar for the following languages: $$\{w\...