Tagged Questions

22 views

w such that contains at most two 1s, CFG idea

this is my first time that I did a CFG and I ask if it's correct or not. My idea is the follow: A -> 0A | 1B B -> 0B | 1C C -> 0C As the CFG has to ...
46 views

Context free grammar $L=\{a^ib^jc^k|j=i+k-2\}$

$L=\{a^ib^jc^k|j=i+k-2\}$ This expression surprise me a lot and put me into deep thinking. what i am doing by solving the expressions: ...
33 views

Deterministic Push-Down Automata

Does there exist Deterministic Push-Down Automata for the language below. Any kind of answer will be highly appreciated! $$L =ba^nb^n U bba^nb^{2n}$$
15 views

Collapsing adjacent states in a grammar

I am trying to write a program which can induce a grammar from an example of the code(really more of a corpus than an example). I'm ignoring the decision problem, because I am doing two things that ...
24 views

Checking my CFG to CNF answer

I attempted to transform the given CFG into CNF. $$S → ASA|A$$ $$A→aa|ε$$ Here are my steps: $$S→X$$ $$X→XA|AX|A$$ $$A→aa$$ $$S→X$$ $$X→XA|AX|YY$$ $$A→YY$$ $$Y→a$$ $$S→XA|AX|YY$$ ...
22 views

CFG Convertion to GNF

I have a very simple CFG that I am trying to convert into GNF. The CFG is: S -> aSbS S -> epsilon I looked at the CFG and I think I can just do the ...
21 views

59 views

Proving that a language is not context-free

Given the language $$L = \{ a^p \mid p\, \text{IS NOT prime} \}$$ is $L$ Context free? If not, prove that it's not. May I have some suggestions on how to use the pumping lemma to prove this, ...
44 views

Difficulty finding context free grammar for this language

I'm learning context free grammars from languages. Language ${L=\{{a}^{2i}\,{b}^j\,{c}^k\,|\,3i=j+k, i \gt 0\}}$ My guess is $${S\rightarrow BA}$$ ...
56 views

Context free grammar for language

I'm learning how to generate context-free grammar for a language. $L=\{{a}^i {b}^j {c}^k\, |\,i=j\lor j=k$ Here is how I tried ...
84 views

Prove context-free or not context-free

Given the following language: $L=\{a^{p^2}|$ $p$ is prime$\}$ How can I show that this language is not context free using the pumping lemma? I'm having trouble breaking it up to $s = uvxyz$. would ...
76 views

Push down automata for context free grammar

I'm having trouble finding the PDA for this language $L = \{x^{3i} y^j z^k\ |\ i \ge 0 \land k \gt 2j \gt 0\}$ The ...
56 views

Closure properties!

If $L_{1}$ is a context-free language and $L_{2}$ a regular one,use the closure properties and explain if the language $L_{2}-L_{1}$ is also context-free or not.How can I do this?
54 views

Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...
39 views

Consider this grammar

Consider this grammar: \begin{array}{l} S \to aabBba \mid aAb \mid aab \\ bBb \to bCa \mid aaa\\ aA \to aC \mid bba\\ C \to aab \mid Cb \end{array} This is clearly context-sensitive (CS). It's not ...
76 views

Write a grammar that generates the strings over {a,b} starting with a

The answer is: S -> aA, A -> aA, A -> bA, A -> a, A -> b, S -> a Any idea how they got this?
154 views

Grammar Construction from Given Language!

Just a fast question! I have this language L(G) = { z^n * x^2n with n>=1 } What is the grammar ? I think it should rather be: ...
114 views

32 views

Grammar derivation

Given these grammar productions: \begin{align*} &S\to A1B\\ &A\to 0A\mid\lambda\\ &B\to 0B\mid 1B\mid\lambda \end{align*} And given string $w = 01101$ If I wanted to make a) ...
48 views

Showing a grammar to be ambiguous

I'm learning about grammar ambiguity and trying to show the following grammar is ambiguous: $S \rightarrow ScS | SdS | A$ $A \rightarrow a | b$ I used 2 different left-derivations to get the same ...
40 views

CF grammar on this language

I'm trying to write a context-free grammar for this language: $L = \{a^n b a^m (bb)^n : m \ge 1, n \ge 0\}$ I was getting lost with maintaining $n$ number of $a$'s and $(bb)$'s and I'm not sure how ...
241 views

Lambda productions in grammar

I tried removing the $\lambda$ productions from this grammar: $S \rightarrow a A b \mid B B a$ $A \rightarrow b b \mid \lambda$ $B \rightarrow A A \mid b A a$ It seems like you just take away the ...
30 views

S-grammar for this regular expression

Given this regular expression: $r = a a^* b + b^* c b$ I think this is the simple grammar, but I was getting a little lost with the productions: $S \rightarrow S_1 | S_2$ $S_1 \rightarrow a A b$ ...
139 views

Greibach normal form conversion

I'm trying to convert this into GNF: $S \rightarrow ASaa | bab$ $A \rightarrow Ba | bAB$ $B \rightarrow abba$ So I'm getting this, but I'm not sure understanding and applying correctly the concept ...
83 views

Grammar into Chomsky Normal Form

Convert the following grammar into Chomsky Normal Form (CNF): S → aS | aAA | bB A → aA | λ B → bB | aaB I think this looks ok, but not sure. Maybe someone can point out where I go wrong: ...
412 views

Designing Context-Free Grammars for Sets of Strings

I'm pretty lost, and would appreciate help or solutions to the following two exercises. I don't really know where to begin or even how to correctly denote a context-free grammar. I have to design CFGs ...
208 views

Every Regular Language is a Context Free Language

How do I show that every regular language is a context-free language? I've been told to construct a Context-Free Grammar by Induction on the number of operators in the regular expression; but I'm ...
112 views

Right-Linear Context Free Grammars

Following is a problem that I have no idea how to solve. I'd appreciate someone showing me how to solve this problem. A CFG is right-linear if each production body has at most one variable, and ...
84 views

why is {a^nb^n} context-free?

I am writing somthing about Ppumping Lemma. I know that the language L = { a^nb^n| n ≥ 0 } is context-free. But I don't understand how this language satisfies the conditions of pumping lemma (for ...
208 views

CFG - whose words contain exactly twice as many b's as a's.

I am trying to built a CFG for the language that accepts all words that have twice as many b's as a's. The only idea I could come up with is: Start -> S S-> SaSbSbS | SbSaSbS | SbSbSaS | $\epsilon$ ...
102 views

Understanding how to convert a PDA to a CFG

Given a PDA, initialized with $\#$ on the stack, and with accepting states $q_a, q_b, q_c$ and the following transitions: (current state, stack head, input character, replacement for old stack head, ...
130 views

Languages with context-free grammar having only one non-terminal symbol

As seen in this question, the class of languages that can be generated by a context-free grammar having only one non-terminal symbol (i.e. the start symbol) is a proper subclass of the class of ...
167 views

Formal Reduction: Pushdown Automata recognizing context free languages with bounded stack

I am studying for an exam in automata theory and I am having trouble solving the following: Consider pushdown automata and context free languages. Show that the following decision problem is ...
420 views

A computer's memory is finite, so how can there be languages more powerful than regular?

A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the ...
$L=\{ xcycz : x,y,z \in \{a,b\}^* \wedge xy, \ yz - \text{palindromes} \}$ Is $L$ context free language?