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
26 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
23 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^\...
1
vote
1answer
32 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 ...
0
votes
1answer
34 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
92 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
43 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
55 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
20 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
19 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
30 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
68 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
307 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
28 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
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 \...
0
votes
1answer
30 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
26 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 ...
0
votes
0answers
27 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 ...
2
votes
1answer
175 views

How to simplify context free grammars?

How to simplify this context-free grammar? $$ S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b $$ Can the simplification result in this CFG? $$ S \...
2
votes
1answer
81 views

Context-free Grammar Exercise

Could someone explain me how to form a context-free grammar with all rules R by this example language, please? \begin{equation} L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\} \end{...
2
votes
1answer
71 views

Can there be a context free language that is not recognizable by a PEG?

This is related to this question. Essentially, I want to know whether my reasoning is correct. We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: ...
1
vote
0answers
30 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
34 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
2answers
38 views

Difference between $a^{2n} b^n$ and $n_a(w) = 2n_b(w)$

I have encountered two questions related to npda: Construct an npda for $L_1 = \{a^{2n} b^n \mid n \geq 0\}$ as a language over $\Sigma = \{a,b,c\}$. Construct an npda for $L_2 = \{w \in \{a, b, c\}^*...
1
vote
1answer
54 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 ...
0
votes
0answers
11 views

can a PDA without lamda-transition accept every context free language? [duplicate]

I want to know if every context-free-language can be constructed with a PDA without lambda transitions. I have tried to give a counter example but couldn't. Is there a theorem proving such statement ...
0
votes
0answers
23 views

Converting an NPDA to a CFG

I have a question regarding conversion of NPDA to CFG. The above picture is from my lecture slides. I dont understand why they are saying 1 can be popped while transitioning from q0 to q1. It is in ...
1
vote
1answer
38 views

Making a CFG for a^i b^j c^k such that i+k < 3j

I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG. I have thought about solving this for a long time but but this still hasn't gotten me ...
4
votes
1answer
317 views

How to determine if a language is deterministic context-free language?

I have the following question to solve : DCFL means Deterministic Context-Free Language. Let $L$ be a DCFL over an alphabet $\Sigma$. For each of the following functions of $L$, determine whether $...
2
votes
1answer
241 views

Example of non-regular context free language L such that prefix(L) is regular

Suppose we have some non-regular context free language L. Suppose we also have language of all prefixes of words in L. What can be an example of non-regular language L such that language of it's ...
1
vote
0answers
56 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$ . ...
1
vote
1answer
19 views

Variable derives itself

In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim. Consider the grammar: $$ \begin{align*} &R \to XRX \mid S \\ &S \to aTb \mid bTa \\ &T \...
0
votes
1answer
51 views

Does every regular language have a linear grammar?

Some definitions and facts (from Wikipedia): A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions. the left-linear or left ...
0
votes
0answers
20 views

Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free

I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
0
votes
0answers
19 views

Finding a Context- free grammar (CFG) for the language [duplicate]

I am trying to find a CFG for the language A below. I have spent hours on this but still could not find the answer. I also came up with the idea that this may not a context- free language but there is ...
6
votes
1answer
259 views

Are these special (one production) Context-Free Grammars always unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $S \rightarrow aSbS\;|\;\epsilon$ $S \rightarrow ...
1
vote
0answers
24 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 ...
2
votes
1answer
48 views

Does this argument prove CFLs are not closed under union?

Context free languages are not closed under complementation. This follows from their property of non-closure under intersection: If CFLs were closed under complementation, then they must have also ...
2
votes
1answer
73 views

Context-free grammar for $\{a^x b^y : x \neq y\}$

I am trying to create a context free grammar in Extended Backus–Naur form, which starts with a non-empty sequence of a's and is followed by a non-empty sequence of <...
0
votes
0answers
41 views

Pushdown Automata for number of a less than 2 times number of b

Suppose we want to design a pushdown automata for $L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$, can anyone check whether my automata works? we have 4 states $\{q_0,q_1,q_2,q_3 \}$, three stack symbols ...
2
votes
1answer
90 views

Are Context-Free Grammars with only one Production Rule always Unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $\require{cancel} \cancel{S \rightarrow aSSb\;|\;\...
1
vote
1answer
117 views

Is Half - Palindrome subset of a context-free language context-free?

Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a ...
1
vote
2answers
86 views

Proving the decidability of whether a CFG generates a particular string or not

Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$. Consider the language $A_{CFG}$ = { <$G$, $w$> | $G$ is CFG that generates $w$ }, where <$G$, $w$> is a string ...
1
vote
1answer
60 views

Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form

The grammar have the following producitons, \begin{align} S&\rightarrow aTbS \mid\epsilon\\ T&\rightarrow aTb\mid\epsilon \end{align} Already turned this homework in, but I need to convert ...
0
votes
1answer
43 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
0
votes
0answers
40 views

How to find a context-free grammar from a difficult language? [duplicate]

Some Languages are trivial to find their respective context-free grammar. Like for example $ L= \{a^nb^n: n \geqslant 0\}$. However some are really difficult to solve. I would like to have some advice ...
2
votes
1answer
29 views

$L=\{a^ib^i|i\geq0\}$, cfg for $L^2$

$L=\{a^ib^i|i\geq0\}$, cfg for $L^2$ can you write cfg for $L^2$ where $L=\{a^ib^i|i\geq0\}$? the professor's answer sheet says it's $S\to AA\\ A\to aAb|\lambda$ but I think it is wrong because two ...