Help with context free grammar excercise

So, I have an exercise in which I have to write a context free grammar for this language:

$ $ L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$ $

meaning every string with any number of $ a$ ‘s, $ b$ ‘s and $ c$ ‘s in that order, with the amount of $ a$ ‘s greater than the amount of $ c$ ‘s and the amount of $ b$ ‘s greater than zero.

I am having trouble figuring out the rule that makes sure there are more $ a$ s than $ c$ s.

I have: $ $ \begin{align}S&\to aABC | ab\ A&\to aA | a\ B&\to bB | b\ C&\to cC | c\ \end{align}$ $ I know this is wrong because I should be adding an $ a$ every time I add a $ c$ , but I don’t know how to write that.

How to interpret this context free language?

$ S -> aAA$

$ A -> aS | bS | a$

Trivial thing:

starting and ending with a

Atleast 3 a’s are definitely present

(These are very layman observations…but seriously I am unable to figure out what exactly this language is all about. …) My attempt:

What I am able to generate



a bS A

a ba AA A

a ba ***

This suggests after b there should be atleast 1 a

*(Coz those *** have all

  1. a’s


  1. if bS used then again a ‘ba**’


  1. if aS used length also increases by atleast 3.)*

I know this is not a good analysis..and so I am not expecting any answer but would definitely expect some comments about some intuition or idea..plz any help would be much regarded..

(Although answers are always welcome 😉 )

Are there context free grammars for all restricted Dyck paths?

A Dyck path is a finite list of $ 1$ ‘s and $ -1$ ‘s whose partial sums are nonnegative and whose total sum is $ 0$ . For example, [1, 1, -1, -1] is a Dyck path. Rather than use $ 1$ and $ -1$ , it is common to use "U" and "D" for $ 1$ and $ -1$ , respectively, so we might write UUDD instead. (These might be more familiar as Dyck words.)

It is well-known that Dyck paths have a standard "grammar." The "Dyck grammar" for a path $ P$ is

$ $ P = \epsilon \quad | \quad U P D P.$ $

This grammar is very useful because it lets us quickly compute the generating function which enumerates the number of Dyck paths of given lengths.

I am interested not in all Dyck paths, but restricted sets of Dyck paths. For example, consider the Dyck paths which avoid "peaks" (the bigram UD) at positive even heights; UUUDDD is such a path, while UUDD is not. If we could devise an unambiguous grammar for such paths, then we could write down an equation for the generating function which counts them. (There is such a grammar. It requires two production rules – one for the paths which avoid peaks at even heights, and one for paths which avoid peaks at odd heights.)

This idea leads to a natural question:

Given a (possibly infinite) set of positive integers $ A$ , does there exist a finite, unambiguous context-free grammar which generates precisely the Dyck paths whose peaks avoid $ A$ ?

The answer (I think) is "yes" when $ A$ is finite or an arithmetic progression. I suspect that the answer is "no" in every other case, but I have no idea how to begin proving this.

For example, here is a special case that I cannot decide:

Is the set of Dyck paths which avoid peaks at positive squares a context-free language?

Applied Pi calculus: Evaluation context that distinguishes replication with different restrictions

For an exercise, I need to find an evaluation context $ C[\_]$ s.t. the transition systems of $ C[X]$ and $ C[Y]$ are different (=they are not bisimulation equivalent), where $ X$ and $ Y$ are the following processes:

$ $ X = ( \nu z) (!\overline{c}\langle z \rangle.0)$ $ and $ $ Y= !((\nu z) \overline{c}\langle z \rangle.0)$ $

Intuitively, the difference seems to be that in process $ X$ , all replications of the process output the same $ z$ on channel $ c$ , while in process $ Y$ , all processes output a different $ z$ . Is this correct? And how could this be used to construct an evaluation context such that $ C[X] \neq C[Y]$ ?

How to convert FDA to context free grammar?

I have an assignment, which is solved by making an FDA out of the information given, then figuring out the CFG out of the FDA, but I’m having trouble doing that step. Any help is appreciated! Here is the picture of the exercise:

Picture of the excercise

A token is dorpped from A, B or C. The two keys (-.- these things) make the token go right or left depending on the position in which they are in (the token falls parallel to the direction of the key). When a token passes through a key, it makes it switch positions so that the next token that passes through goes in the opposite direction than the last.

What I have to do is write a program in python that, given a string (eg ABCAAAC, meaning a token was dropped from A, then another from B, then another from C, etc.) I have to determine wether or not it belongs to the language composed of the strings in which the last character (the last tken dropped) falls from exit one. To do this, first I figured out the automaton that models this behaviour, and the next step would be figuring out the grammar for that language by looking/doing smth with the FDA (I have to do it this way, not with regex).

Here is the picture of the FDA, I’m not sure it’s correct:

Here is the image of the automaton I made

Does all derivation trees generated by context free grammar in cnf form can be recognized by buttom up tree automata?

G is a context-free grammar in Chomsky normal form.

we define L(G) to the set of all derivation trees that formed by G.

Is it possible to create a non-deterministic bottom-up tree automaton that will accept L(G) exactly? if so, how to construct such automaton?

I think it’s true, so I’m trying to construct the automaton but having hard time to define specifically the transition function.

hope to get help.