Questions tagged [context-free]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
9 views

How to create a LR(k) grammar for an arbitrary k

Is there a simple procedure for constructing a grammar that is LR(k) but not LR(k-1) for any k?
4
votes
2answers
423 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
0
votes
1answer
11 views

Does there exist an algorithm to generate the production rules of CFG, given a sample production?

Lets say, we provide the algorithm a set of tokens. e.g. x + y - z x - x - x It will then try to generate a CFG which fits all the provided examples ...
1
vote
2answers
36 views

Context-free grammar for ${a^n b^n a^n}$

I am trying to figure out a formal grammar for the above language. This language describes palindromes, so it is context-free, if I am not wrong. I came up with a context-sensitive grammar, but I can ...
0
votes
0answers
19 views

How to include both precedence and associativity in following grammar?

For the following grammar, how can I include both precedence and associativity of operators: S -> S|S S -> S.S S -> S* S -> (S) S -> a|b Note: In the first rule ...
3
votes
2answers
642 views

Why do we not use CFGs to describe the structure of lexical tokens?

This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff. Here is my current answer: CFGs describe how non-terminal symbols are converted into ...
1
vote
1answer
42 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 ...
0
votes
2answers
95 views

Prove using pumping free lemma for context-free languages

One of the exercises I tried to make I failed miserably. The question was as follows: Show that the language $L = \{ w \,|\, n_a(w) \cdot n_b(w) = n_c(w) \}$ is not context-free. (with $n_a(w)$ ...
0
votes
1answer
31 views

Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?

My assignment asks Let $S = \{ w_1\#w_2\# \dots \#w_k | k ≥ 2; (∀i ≤ k)w_i ∈ \{0, 1\}^\star ; (∃i < k) w_i\neq w_{i + 1}^r$ , i.e., not every string $w_i$ is equal to the reversal of $w_{i+1}$. ...
0
votes
1answer
42 views

Is this a CFL: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$?

I recently found a question asking whether the language given below is context-free or not: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$ My intuition is that I can design a non-deterministic push-down ...
1
vote
0answers
33 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 ...
0
votes
1answer
39 views

Need help with previous “Automata / Theory Of Computation” exam question

I passed by this question in a previous exam while studying for the "Automata / Theory Of Computation" and I am struggling to find answer. I would appreciate it if someone can help me with it: This ...
3
votes
2answers
127 views

If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?

I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack. But, a link of Show that { ...
1
vote
1answer
25 views

Developing a Context Free Grammar whilst knowing the number of terminals

I am trying to develop a CFG for the language $L$ defined by: $L = \{a^{n+2}bba^{n-2} | n > 1\}$ The problem I am having is that I cannot develop the CFG for this language no matter what I try. ...
1
vote
1answer
54 views

Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
2
votes
3answers
3k views

Why are DCFL not closed under concatenation or Union whereas CFL is?

I understand that DCFL they are not closed under concatenation or Union. As without non determinism, PDA cannot decide when to jump to the next one in case of concatenation and without epsilon moves ...
0
votes
1answer
19 views

Convert CFG to CNF Arithmatic Expression

Convert CFG to CNF The Grammar E→E+T E→T T→T*F T→F F→(E) F→x Step 1 Assign variables to terminals A→ + B→ * C→( D→ ) F→x ...
-4
votes
0answers
35 views

automata and context free languages

Theory of automata is study of abstract machines, like Turing Machines, Finite State Machines, Push Down Automata, Mealy and Moore Machines. You have to discuss and explain which kind of automaton ...
-2
votes
2answers
1k views

Can the CFG model Kleene star (even when it can be $\epsilon$-free)? How?

Can the context-free grammar model the Kleene star * operation of regular expressions? If the CFG is reducible to not containing $\epsilon$ productions, as per: ...
2
votes
1answer
336 views

What's wrong with this LL(1) grammar?

I am trying to build a LL(1) parse table for the following grammar: S -> L L -> L : L L -> id R R -> ( L ) R -> ( ) R -> Epsilon There are two ...
0
votes
1answer
56 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
votes
0answers
21 views

Creating language $L_1$ with given parameter

Suppose $G$ is a context-free grammar, the language $L_0⊆\Sigma^*$ is also context-free but not-regular and $\#\not\in \Sigma$. Using $L_{(G)}$, $\#$, $L_0$, and $\Sigma^*$ create language $L_1$ such ...
0
votes
1answer
21 views

Creating a PDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}

I didn‘t find a DPDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}, so I guess an NPDA is the only option. NPDA are not very intuitive to me. The only solution I found online is: I don‘t ...
1
vote
1answer
39 views

Can there be a language not Context free but still PDA acceptable?

Let the input alphabet be $Σ = \{1,x,=\}$ Let the stack alphabet be $\tau = \{1,\$\}$ where $\$$ is the initial stack symbol. Let,$q_0$ be the initial state of the PDA,$q_f$ be the final state of PDA,...
1
vote
2answers
66 views

How Intersection of Regular Language and a CFL is a CFL?

CFL is not closed under intersection. That means, if we have L1,L2 of CFL then L1 intersection L2 is not a CFL And we know, all Regular languages are CFL. Then ...
0
votes
0answers
33 views

is L not decidable? [closed]

Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$. Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable? But isn't $L$ decidable since it is possible to ...
2
votes
1answer
56 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
0answers
32 views

Why is a Context Free Grammar that is simultaneously in Chomsky Normal Form and Greibach Normal Form regular?

In my course materials, there is one sentence about how if CFG is in Chomsky Normal Form, it is not regular, and if it is in Greibach Normal form, it also is not. But when a grammar is simultaneously ...
1
vote
1answer
27 views

Algorithm to generate inputs with certain properties, but not accepted by a given regular language

General Given a regular language $L \subset \Sigma^\star$, I wish to generate at least one string not in $L$. (Obviously, this requires that there exists such a string; i.e., that $L \neq \Sigma^\...
0
votes
1answer
40 views

Using the pumping theorem to show that this language is not context-free

Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i*j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free. I really don't know where to start, here. ...
10
votes
1answer
324 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
21
votes
3answers
1k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
3
votes
3answers
2k views

Are regular and context free languages closed against making them prefix-free?

For a language L we define: $\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $ Are regular / context free languages closed under this operation ? For regular languages I ...
2
votes
1answer
97 views

Prove/disprove: If $𝐿_1$ is a finite language but not empty and $𝐿_2$ is NOT regular then $𝐿_1 \circ 𝐿_2$ is NOT regular

That what I have so far, but I am not sure at all. Assume toward contradiction that $𝐿_1 \circ 𝐿_2$ is regular. Define $\Sigma' = \{\sigma'|\sigma\in\Sigma\} $. Define a regular substitution $\...
1
vote
1answer
37 views

Regular Language - Context Free Language

I know this is not a question answer posting site but for the sake of explaining my doubt I will like to post a question Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet $\...
2
votes
1answer
45 views

Closure properties of non-context-free languages (concatenation & complement)

I am trying to proof the properties of the complement and concatenation of two non-context-free languages $L_1$ and $L_2$. I believe that both of these languages are closed under complement and ...
0
votes
0answers
56 views

I´m having problems with this Context Free Grammar

I am not able to convert the following language to a Context Free Grammar. The major problem is how to pump both "sides" of the word to obtain same number of 0s and 1s, but, without creating a series ...
2
votes
2answers
58 views

Is the difference of two context-free languages still context-free?

i am asking myself the following question: Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right? but I do not know how to prove it.
0
votes
0answers
24 views

Proving sets of regular expressions and context free grammars are decidable [duplicate]

Consider below languages: $L_1=\{<M>|M$ is a regular expression which generates at least one string containing an odd number of 1's$\}$ $L_2=\{<G>|G$ is context free grammar which ...
0
votes
0answers
30 views

Understanding PDA for odd length string with middle symbol 0

I came across this pdf, which describes the language of odd length string with middle symbol 0 as follows: Doubts: I dont understand the transition labels. In standard resources like books by ...
1
vote
1answer
55 views

Formal languages: What is $2n_c$?

I have got following question: Determine whether the following language is context free or not: $$L = \{ w \in \{a,b,c\}^*: n_a (w) = n_b (w) = 2n_c (w)\}. $$ What is the meaning of $2n_c$ in the ...
1
vote
0answers
43 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 ...
0
votes
2answers
121 views

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?

I understand the difference in the parsing tables of the above 4 parsers. I understand that CLR>LALR>SLR>LR(0) in terms of power. Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),...
1
vote
2answers
77 views

Is a^mb^n where m=n^2 a CFL?

Is $a^mb^n$ where $m=n^2$ a CFL? I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right? On the other hand I ...
1
vote
3answers
483 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 ...
4
votes
1answer
316 views

Prove that the class of CFG languages that are closed under reversal is undecidable

Note The wording of the title may be a bit vague, but I'm not asking if CFLs are closed under reversal. Please see below. Problem Description Given a word $w$, define $w^{r}$ to be its reversal. ...
7
votes
2answers
1k views

DCFL with prefix property have LR(0) grammar?

There are two important theorems about LR(k) grammars and DCFL. Mentioned here. A language has an LR(1) grammar iff it is DCFL. A language has an LR(0) grammar iff it is DCFL and has prefix property. ...
1
vote
2answers
112 views

CFG - Left factoring in recursive nested productions

I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
0
votes
1answer
33 views

Deterministic pushdown automaton for a given language

I am trying to make a deterministic pushdown automaton from this language but without success. Here is the language definition: $\ L=\{0^n 1^m a^i b^j \ /\ m,n,i,j > 0 \ and \ m+n=i+j \} $ ...
1
vote
1answer
38 views

Find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$

I want to find a Context-Free Grammar for $L:=\{a^nb^mc^{n+m}\mid n,m\in\mathbb{N}\}$ I've tried the following: $G=(V,\Sigma,R,S)$ with $\Sigma=\{a,b,c,\lambda\}$, $V=\{S,B\}$, $S=S$ and $$R=\{S\to \...

1 2 3 4 5 25