1
vote
1answer
36 views

PDA and Some language Grammar inference

L1={$w^* $| w=x and $ x \in \Sigma^*$} L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
2
votes
1answer
59 views

Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
0
votes
1answer
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 ...
1
vote
1answer
50 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: ...
1
vote
1answer
36 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}$$
2
votes
0answers
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 ...
1
vote
1answer
30 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$$ ...
0
votes
0answers
23 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 ...
0
votes
0answers
22 views

Show L is not context free using the CFL pumping lemma

I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$ So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 > m$. We can decompose $z = ...
0
votes
1answer
28 views

Prove a language is Context Free

I am working on the following problem and I do make a little progress. Let me state the question first: Prove that the set of strings consisting of $a$'s and $b$'s with an equal number of $a$'s and ...
1
vote
1answer
32 views

There is a sequence of operations on grammars of a string that strictly decreases the size of grammars down to the smallest grammer.

I'm trying to figure out the smallest grammar problem, which yes I know is impossible since it's such a hard problem, but humor me for a sec. Let $g$ be a smallest grammar for the string $s$ over the ...
0
votes
0answers
21 views

Eliminate Useless Productions

How do I eliminate useless productions from the grammar: $S \rightarrow a|aA|aaB|abC$ $A \rightarrow aB|\lambda$ $B \rightarrow Aa$ $C \rightarrow cCD$ $D \rightarrow ddd|aC$
0
votes
1answer
18 views

Eliminating Unit Productions

Eliminate all unit-productions from the grammar: $S \rightarrow abA\:|\:A\:|\:B$ $A \rightarrow B\:|\:ba\:|\:aBA$ $B \rightarrow A\:|\:aa\:|\:aA$ An article I was reading said that a unit ...
1
vote
1answer
50 views

Is the language $L=\{ww^f|w\in \{0,1\}^*\}$ CFL?

Where $w^f=$flipping the bits of w. For example, $(0010)^f=1101$, $(010111)^f=101000$ I tried to prove that $L$ is not CFL using the pumping lemma, with no succeed. In addition, I need to prove ...
0
votes
1answer
40 views

Creating a Push Down Automaton from a Grammar

I have the following grammar, but I'm not sure what exactly it is that it does: $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid \thicksim p ...
4
votes
1answer
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, ...
1
vote
1answer
45 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}$$ ...
2
votes
1answer
57 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 ...
1
vote
2answers
85 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 ...
1
vote
1answer
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 ...
1
vote
1answer
57 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?
2
votes
1answer
111 views

Converting Context Free Grammar to Chomsky Normal Form

This is an exercise that I had to complete in my class and I struggled a lot with it $$\begin{align*} &S\to 0A0\mid 1B1\mid BB\\ &A\to C\\ &B\to S\mid A\\ &C\to S\mid\epsilon ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
95 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?
0
votes
1answer
156 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: ...
1
vote
1answer
127 views

Languages and Grammar (Finding a language)

I have a trivial question (that I have actually solved, hopefully) although I am a bit curious if my result is alright. We have $N= \{S , C ,D\}$, $T=\{c, d\}$ and $P = \{S \to Dc, D \to Dd, D \to ...
0
votes
1answer
22 views

What is the Language $L(0^*)$?

While working on Formal Language Theory, I came across this expression: $L(0^*)$. What is meant by this? I know that $0^*$ is the set of all strings over the symbol $0$. So is this language the set of ...
0
votes
1answer
67 views

Verification: Proof that the Context-Free Languages are Closed under Reversal

Here's the problem: Prove that the context-free languages are closed under reversal. Here's my work: We want to show that if $L$ is a context-free language, then $L^R$ is a context-free ...
1
vote
1answer
59 views

Dicrete Mathematics (Languages Grammars)

Given Grammar $G$ with non-terminal symbols $N= \{S, A, B, C\}$ and terminal symbols $T=\{a,b\}$ and derives $P=\{ S \to B , B\to aBa, B\to bA, A\to bA , A\to C, C\to a \}$ and start symbol is S. ...
3
votes
2answers
47 views

Injective map, that maps context-free languages to regular languages

Let $\Sigma \neq \emptyset$ be an alphabet. Is there an injective map $f: \Sigma^* \rightarrow \Sigma^*$ such that for every context-free language $L \subseteq \Sigma^*$ the set $f(L)$ is a regular ...
0
votes
1answer
217 views

Using the Pumping Lemma to Prove $L = \{a^ib^jc^k \mid i < j < k\}$ is not Context-Free

I want to use the Pumping Lemma to prove that $$L = \{a^ib^jc^k \mid i < j < k\}$$ is not context-free. I think I have the intuition, but I don't know how to prove it. Help?
0
votes
1answer
65 views

Finding a context-free grammar for a language with a different word count condition

I want to find a context-free grammar with the condition, that the grammar has to be the complement of a language with the same word count. So a language with the same word count can be specified ...
0
votes
2answers
292 views

How to create a grammar for complement of $a^nb^n$?

I've got a language L: $$ \Sigma = \{a,b\} , L = \{a^nb^n | n \ge 0 \} $$ And I'm trying to create a context-free grammar for co-L. I've created grammar of L: ...
0
votes
0answers
25 views

CF grammars and productions that are not CF

I'm learning about CF (context-free) grammars and I thought I understood what CF meant but I want to make sure I'm getting this concept. So I'm using some examples to make sure I'm understanding: $S ...
0
votes
1answer
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) ...
0
votes
1answer
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 ...
2
votes
1answer
41 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 ...
2
votes
2answers
249 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 ...
0
votes
1answer
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$ ...
1
vote
1answer
140 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 ...
0
votes
1answer
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: ...
0
votes
2answers
437 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 ...
0
votes
1answer
215 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 ...
0
votes
1answer
115 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 ...
1
vote
2answers
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 ...
1
vote
1answer
215 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$ ...
0
votes
1answer
103 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, ...
5
votes
1answer
133 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 ...
3
votes
1answer
172 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 ...