The tag has no wiki summary.

learn more… | top users | synonyms (1)

1
vote
1answer
23 views

Context-Free Grammar construction when order isn't specified

I'm having trouble constructing a grammar for L={wϵ{a,b}|na(w)≠nb(w)} So I need to construct a grammar for the language wherein the number of a's does not equal the number of b's. The farthest ...
1
vote
1answer
28 views

CFG for language

I can't find CFG for this language. $N = \{w ∈ \{0, 1\}^* \mid \text{w contains more } 1\text{s than }0 \text{s}\}$ Basically, it is much easier when order is set (for example, $1$s come after $0$s) ...
1
vote
2answers
36 views

Are regular languages necessarily deterministic context-free languages?

The original problem Suppose M is DCFL (Deterministic Context Free Language) and N is a regular language. Answer the following questions and justify your answers. a) Is M-N necessarily context-free? ...
4
votes
1answer
40 views

Is any formal language with given restriction context free?

Consider formal language $L$ in which each word has non-trivial period (non empty prefix that is also a suffix) over finite alphabet. Is $L$ context free? I think that $L$ can be non context ...
1
vote
1answer
26 views

Are these two context free grammars equivalent?

Let Σ = {a,b}. A CFG for the language {a^nb^m | n > 2m} can be written as: S-->aaSb S-->A A-->aA A-->a Would it be equivalent to write this CFG as: ...
0
votes
0answers
13 views

Precedence Relation Table and Bottom-Up parsing

I have following rules: E->E+T|T T->T*P|P P->(E)|V I need to create a precedence relation table. It is said that it can be accomplished Wirth-Weber ...
0
votes
0answers
25 views

Weak Precedence Grammar and Bottom-up parsing

I am studying parsing, i.e. bottom-up parsing. it is said that there some rules which are used by weak precedence grammar. What does weak precedence grammar mean? What about precedence relation? Any ...
0
votes
1answer
33 views

Homorphism and Context Free Grammar

Could you explain me concept of homomorphisms and usage of it to the following problem which requires to prove that $L$ is not context-free? $$L=\{ba^{n-1}ba^nb:n\ge 1\}$$ Thanks
0
votes
1answer
32 views

Pumping lemma and CFG

I am solving problem in pumping lemma for context-free languages. I want to ask a hint for the following problem $$L=\big\{www:w\in\{a,b\}^*\big\}$$ Thanks
0
votes
1answer
38 views

Pumping lemma for CFG

it is another my question. Can you give me hint to solve the following problem? Prove that $L=\left\{a^{n^2}:n\ge 0\right\}$ is not a context-free language? Thanks!
0
votes
1answer
23 views

CFG and closure properties

I am solving one problem and I urgently need a hint to solve one problem: Use closure under union to show that the following language is context-free $$\left\{a^mb^nc^pd^q : n=q,\ \text{or}\;\ ...
1
vote
1answer
39 views

Which one of these language Context free?

Which one of the following languages is CFL and what is the grammar for it? Can we use pumping lemma for the not CFL? \begin{align*} L_1 &= \{a^mb^ma^n \mid m,n \geq 0\}\\ L_2 &= \{a^mb^ma^n ...
1
vote
1answer
54 views

How to construct a context free grammar $G$ such that $L(G) = \{ 0^i 1^j 0^k| j \gt i+k\} $?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j a^k| j \gt i+k\} $? My attempt: $G_1 = (\{ S,A,B\}, \{a,b\},P,S)$ where $P$ consists of: $$ S\to AbBC $$ $$A \to ...
1
vote
1answer
44 views

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\} $? I don't have much idea how to approach this one. Could some help me to understand how to approach these ...
0
votes
1answer
57 views

Find context free grammar and prove its correctness

Find context free grammar for a given language and prove its correctness: a) $\left\{ a^ib^ja^k : i\neq j \ \vee \ j\neq k \right\}$ b) $\left\{ w\in \left\{a,b\right\}^* : \#_a(w)=2 ...
0
votes
1answer
51 views

Context free grammar to language

Suppose we have $G(V,Σ, R, S)$ where $$\begin{array}{ll} V & = \{a,b,A,B,S\}\\ Σ & = \{a,b\}\\ R &= \left\{ \begin{array}{rl} S &→ abA,\\ S&→B,\\ S&→baB,\\ S&→e,\\ ...
0
votes
1answer
36 views

Context Free Grammar for $L = \{0^n w 1^n \mid n \ge 0, w \in \{0, 1\}^*\}$

Title says it all. I'm trying to make sure I have the correct CFG for $L$ before I start converting it to GNF. I don't want to post my idea yet, as I don't want it to influence any of the replies. ...
0
votes
0answers
50 views

Pumping Lemma length, $K$ for context-free language

Please help me understand, and if possible, tips, to determine a pumping length $K$. Suppose I have the example : Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,T\}$, set of ...
0
votes
0answers
33 views

Chomsky Normal Form solution for a problem

Here is my attempt at CNF, Original: $$ \begin{align*} S &\to 1 A \mid O B \\ A &\to O B O \mid 1 0 \mid \epsilon \\ B &\to A 1 A \mid 0 1 \end{align*} $$ CNF: $$ \begin{align*} S ...
2
votes
0answers
21 views

defining relationship between geometric entities (features)

I have different features located on a plane (2D); I want to define this structure mathematically in a way to represent their relations. Some of features are aligned in horizontally, vertically or ...
2
votes
1answer
88 views

Show that this language cannot be accepted by a deterministic push-down automaton [duplicate]

How do you show that there exists no DPDA that accepts $ L = \{0^n1^n \} \cup \{ 0^n1^{2n}\}$ ?
1
vote
1answer
73 views

Finding a context-free grammar for $a^i b^j : 2i < j$

So I have a question: Give a CFG for $a^i b^j : 2i < j$. And this is my approach: $$S \to AB$$ $$A \to aAb | e$$ $$B \to b | bB$$ Thanks, a confirmation, or correction, along with how you ...
2
votes
1answer
33 views

My approach to a CFG

this site has been of great help, and I am certainly indebted to your assistance. I was solving a question, $a^i b^j$ where $0\le i\le j\le 2\cdot i$ And here is my approach: $S\to aSb \;|\; aSbb ...
2
votes
1answer
49 views

Constructing PDA with either one state or two states

If $L$ is a context-free language and $\epsilon \notin L $, how do you show that there exists a PDA that accepts the language by final state such that it has not more than two states and makes no ...
1
vote
1answer
46 views

$w$ such that it contains at least 3 ones, is my approach to the CFG right?

So I was trying to solve the CFG, $$\{w \in (0,1)^* \mid w \text{ contains at least three 1's}\}$$ My approach: I decided that a string can begin with a $0$, end with a $0$, it may begin with a ...
1
vote
1answer
43 views

A CFG for the language $\{ O^i 1^j 2^k 3^l : i=k, j>1 , l>0 \}$: Is my approach correct?

I am trying to construct a CFG for the CFL $\{ O^i 1^j 2^k 3^l : i=k, j>1 , l>0 \}$. When given $i=2$, $k=2$, $j=2$, and $l=1$, this yields the string $0011223$. My approach: $$\begin{align} S ...
0
votes
1answer
29 views

Infinite context free subset

Disprove that: Given an infinite recursive language $L$, there exists an context free, infinite subset $A$ of $L$. This was asked in the exam. Any hint/partial solution?
3
votes
2answers
48 views

Is my context free grammar here correct?

So in preparation for an interview, I have been revising and studying by solving some CFGs, and here is a question, which I solved, but I feel like I haven't solved it right, given its boundary ...
1
vote
1answer
41 views

Decidability Turing Machine Problem

$L=\{G|G$ is a context free grammar over ${a,b}$ and $L\{G\}$ contains at least one string $w$ such that the number of $a$'s in $w$ is a multiple of $5\}$ Show that L is decidable by ...
2
votes
2answers
57 views

Context free grammar construction

My problem with CFG is, I am to generally create ones but once they have requirements such as: $$\{a^m b^n: m\le n\le 2m\}$$ I have no clue where to begin, and how to approach it. I was wondering if ...
2
votes
1answer
38 views

Proving non CFL with pumping lemma

I can't seem to figure out how to prove this as not a CFL: $$\left\{x^{a}y^{b}\mid a=kb\space\text{for some positive integer k}\right\}$$ I've tried a bunch of "s"'s to pump such as $a^{2p}b^{p}$ ...
2
votes
2answers
61 views

Describe a PDA that accepts all strings over $\{a, b\}$ that have as many $a$’s as $b$’s.

I'm having my exam in few days and I would like help with this Describe a PDA that accepts all strings over $\{ a, b \}$ that have as many $a$’s as $b$’s.
4
votes
2answers
118 views

Push down automata problem

Informally describe the Nondeterministic PDA that generates: $$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$ My initial plan was to use nondeterminism to go through each character before ...
3
votes
1answer
46 views

Context free language problem

I'm trying to find an unambiguous context free language for the ambiguous language: $$S\rightarrow AB$$ $$A\rightarrow Ba| b$$ $$B \rightarrow aA|b$$ I understand the language makes up of strings ...
3
votes
1answer
58 views

Does the Halting Problem apply when evaluating programs that are regular languages?

Here is my understanding of the Halting Problem: It is impossible to write a program H that can determine for any arbitrary program ...
2
votes
2answers
73 views

Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
0
votes
1answer
40 views

Showing the following language is not contex free

I need to show the following language is not context free via the Pumping Lemma. $$L = \{0^n\#0^{2n}\#0^{3n}\mid n \ge 0 \}$$ I was wondering if someone can help explain how to begin such a proof. ...
5
votes
4answers
74 views

Shortest string possible

I was at an interview, and I was asked to give the shortest string generated given this context free grammar. I did not review in years, so I think I got it wrong. What is the answer so I know it for ...
3
votes
1answer
112 views

Context Free Language? Proving through grammar?

I need help solving this question: Is $L = \{ w \in \{a,b,c\}^* \mid n_a(w) = n_b(w) = 2n_c(w)\}$ a context-free language? That is the number of $a$'s equal the number of $b$'s equal twice the ...
0
votes
2answers
274 views

Pumping Lemma to show that a language is not Context Free [duplicate]

I am trying to use the Pumping Lemma to prove that the following language is not context free: $$\{0^n\mid \text{$n$ is prime}\}$$ I am having a really difficult time with Pumping Lemma. Up until ...
1
vote
2answers
75 views

Is L a context free langauge? context-free grammar?

Is $L = \{ a^{(i)} b^{(i)} c^{(j)} \mid i \le j\}$ a context-free language? Would i just create a context free grammar for this?
2
votes
1answer
61 views

Is $L = \{a^{n+2} b^n | n \ge 0\}$ context free or regular?

Is the language $L = \{ a^{n+2} b^n | n \ge 0 \}$ context free? If so, what is a context free grammar for it? If it is regular, what is a right linear grammar for it?
0
votes
1answer
120 views

An infinite context free language can be split into two infinite regular languages

Prove or disprove Let $L$ be an infinite context free language. Show that there exists a regular language $R$ such that $ L \cap R $ and $L \cap \overline{R} $ are infinite and regular.
4
votes
1answer
43 views

Does the following transformation preserve context-freeness?

I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always ...
0
votes
1answer
84 views

Find grammar for given language

I want to practice finding grammars for given languages. Unfortunately after solving some easy examples I found out that I completely don't know how to approach these more ambitious. For example when ...
1
vote
0answers
72 views

If there is an infinite loop in a context-free grammar, is the resulting language context-free?

Suppose I have the following context-free grammar: $ S = A \\ A = aA $ Will the resulting language be context-free? If it is, this would also mean a Turing machine should be able to produce it, ...
0
votes
1answer
138 views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow ...
1
vote
1answer
91 views

Proof of the pumping lemma for Context-Free Languages

I have a doubt concerning the proof of the pumping lemma for context-free languages. The pumping lemma for context-free languages is stated as follows: If $A$ is a context-free language, then ...
2
votes
1answer
295 views

Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
1
vote
0answers
33 views

Non context-free languages closed under reverse

Is this sentence true or false? I'll be glad for some explaination L is not context-free, then its reverse is also not context-free Thanks in advance

1 2 3