# Tag Info

3

"$\lambda$" is commonly used to represent the empty string, although "$\epsilon$" could be the more common one. This was introduced earlier in that book, section "3.1 Grammar Editing" of chapter "Regular Grammars". On the last row you will enter the production $A \rightarrow \lambda$, a $\lambda$-production. To do ...

2

So I worked a bit. And I think I got the answer. Feel free to correct me. S -> aSc | aXc X -> bX | b It works a bit, e.g.: aaaabcccc gets derivation done. Similarly it works for aabbbcc as well.

2

Every such language is finite and regular. Basically, we can think of the grammar as working as follows: we first make a decision for each non-terminal about which way it will expand; then that determines a single word that is accepted in this way. If there are $n$ non-terminals, and each rule as at most $k$ alternatives, then there are at most $k^n$ ...

1

Did you read the slides in the Stanford course? A key point is that it is discussing time complexity for a Turing Machine (TM). Turing Machines are only polynomially equivalent in time complexity to general computers. The precise relationship is found in the slide (in bold for convenience): What it says is: TIME($n^{18}$) All CFLs are in TIME($n^{18}$)...

Only top voted, non community-wiki answers of a minimum length are eligible