# Ullman(Second Edition) Exercise 4.2.3. Question (a) (page no-207)

90 views
Design grammar for the language-

set of all strings of 0s and 1s such that every 0 is immediately followed by at least one 1

is this correct?

S->A | 01S

A->1AS | ε
0
seems to be correct !

## Related questions

1
39 views
Design grammars for the following languages: The set of all strings of $0's$ and $1's$ such that every $0$ is immediately followed by at least one $1$. The set of all strings of $0's$ and $1's$ that are palindromes; that is, the string reads the same backward as forward. The set of all ... of all strings of $0's$ and $1's$ of the form $xy$, where $x\neq y$ and $x$ and $y$ are of the same length.
1 vote
Repeat Question $4.2.1$ for each of the following grammars and strings: $S\rightarrow 0S1\mid 01$ with string $000111$. $S\rightarrow +SS\mid \ast SS\mid a$ with string $+\ast aaa$. $S\rightarrow S(S)S\mid \epsilon$ with string $(()())$ ... $bterm\:\rightarrow\:bterm\:and\:bfactor\mid bfactor$ $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$
There is an extended grammar notation in common use. In this notation, square and curly braces in production bodies are metasymbols (like $\rightarrow$ or $\mid$) with the following meanings: Square braces around a grammar symbol or symbols denotes that these ... is, any language that can be generated by a grammar with these extensions can be generated by a grammar without the extensions.
Show how, having filled in the table as in Question $4.4.9$, we can in $O(n)$ time recover a parse tree for $a_{1}a_{2}\cdot\cdot\cdot a_{n}$. Hint: modify the table so it records, for each nonterminal $A$ in each table entry $T_{ij}$, some pair of nonterminals in other table entries that justified putting $A$ in $T_{ij}$.