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
0answers
8 views

Unexpected output when trying to plot the solution to a system of nonlinear differential equations [closed]

The following Matlab code is meant to plot x(1) vs time and x(2) vs time separately, but only plots x(1) vs time. Despite there being two lines of code to generate each plot, one line is ignored. Does ...
0
votes
0answers
15 views

How can I create the context free grammar for this language? [duplicate]

I need help finding the context-free grammar for this language. $$ L = \{a^ib^jc^k \in \{a,b,c\}^* \mid \text{$i,j,k \geq 1$, and $i=j$ or $i=k$ or both}\}. $$ I've found a way to satisfy $i = j$ ...
0
votes
0answers
21 views

how to write a language for context-free grammar generates the empty string?

How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?
1
vote
1answer
24 views

How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?

This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3. $$ \text {Let }b_i \text{ denote } i \text{...
-1
votes
1answer
23 views

What is the language generated by this grammar?

I'm struggling to find the language generated by the following grammar: Any help would be appreciated.
0
votes
1answer
22 views

Context-free grammar for language involving multiplication

I'm struggling to find the context-free grammar for the following language: $$ L = \{a^sb^tc^m:s,t,m\in\mathbb{N}^+\land1\leq t\leq3\land s\times t=m\} $$ Any help would be appreciated.
-1
votes
1answer
24 views

Find CFG for the following language

I need to show that the following language is context free: $$L = \{a^\ell b^n c^m | \ell, n, m \in \mathbb{N}^+ \wedge ((\ell \ge n) \vee (\ell \ge m))\}$$
0
votes
0answers
26 views

Context free grammar Help

I need to create a CFG for the following language: $$ \{a^ib^jc^k|i≤j≤2i, k=2j\} $$ Getting the a's and c's to be correct is easy enough but everything else is confusing me slightly. any help would ...
-1
votes
0answers
26 views

Context-free grammar for palindrome-like language

I need to give a context free grammar for the following language: $$\{x \in \{d,f,\#\}^* \mid x = u\#v\text{ with }v = v^R\text{ for any }u,v \in \{d,f\}^*\}$$ How would I go about doing this?
-2
votes
0answers
24 views

Right-linear and left -linear Grammar

Could some explain what's the difference between right-linear grammar and left-linear grammar? Maybe on this example: $L:=\left\{w \in\{a, b\}^{*} | w \text { does not contain the subword abaab }\...
1
vote
0answers
20 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 ...
0
votes
0answers
15 views

Proof that $L = \{w | na(w) + nb(w) = nc(w)}\ is not regular [duplicate]

So.. my professor mentioned that it has something to do with $Wi = a^5b^i$ $Zij = c^(i+5)$ which is in the language But then mentioned that $Wj = a^5b^j$ $Zij = c^(i+5)$ Is not in the language, ...
1
vote
2answers
46 views

Is my grammar correct and context free?

I have this language $L = \{a^{n}b^{3n}c^{2m} : m,n \ge 1\}$. I have to determine a free context grammar that generates L. Looks easy BUT i have a question about the grammar I found. First things ...
0
votes
1answer
28 views

How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$

Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s. Also, I have a hint HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...
4
votes
1answer
82 views

Prove or disprove {wtw^R | |w| = |t|} is context free

The language $S_c$ defined as: $S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$ It looks like the language can be "pumped" by context free pumping lemma, ...
0
votes
1answer
17 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?
0
votes
1answer
16 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 ...
0
votes
0answers
22 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 ...
0
votes
2answers
44 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
70 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
votes
1answer
37 views

Set-theoretic difference of two languages in CFL - REG

Let $L_1,L_2\in$ CFL $-$ REG, with $L_1\subset L_2$. Which of the following always holds? $L_1-L_2\in$ CFL $-$ REG and $L_1-L_2\in$ REG. $L_1-L_2\in$ REG and $L_2-L_1\in$ CFL $-$ REG. $L_1-L_2\in$ ...
1
vote
0answers
37 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 ...
3
votes
2answers
161 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
votes
1answer
27 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 ...
1
vote
1answer
30 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. ...
0
votes
1answer
33 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
2answers
41 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 ...
1
vote
1answer
42 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
87 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
36 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
28 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
43 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 ...
1
vote
1answer
41 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
102 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 $\...
2
votes
1answer
60 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 ...
0
votes
0answers
32 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
72 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
0answers
93 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
2answers
92 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 ...
4
votes
1answer
340 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. ...
0
votes
1answer
35 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 \} $ ...
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. ...
1
vote
1answer
39 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 \...
0
votes
1answer
32 views

What is the relation between a programming language and the language of its input?

I find some references say that all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything ...
1
vote
1answer
54 views

Creating a Deterministic Push-Down Automaton for the Union of two languages

Suppose, we have $L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$. Now we want to create a Deterministic Push-Down Automaton for ...
1
vote
0answers
31 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 ...
0
votes
0answers
20 views

Unsure on Proving a Certain Language is Deterministic Context Free

My instructor is stating this is a DCFL. Language in Question: $\{x\in \{0,1\}^* :$ the number of 1's in string $x$ is $>$ the number of 0's $\}$ I can build a CFG to prove this language is ...
0
votes
0answers
27 views

Prove that any PDA/CF language with 1 character is regular [duplicate]

I know there is a post like this already posted, but I didn't quite understand the proof. Can someone explain it to me? Thanks in advance.
0
votes
0answers
13 views

Regular Expression for a^nb^m such that n<= m+3 [duplicate]

I want to know if its possible to write a regular expression for a context free language: For example I have a language : L={a^n b ^m: n<= m +3} I have written the following regular expression ...

1
2 3 4 5
25