Recent questions tagged ullman

Construct a syntax-directed translation scheme that translates arithmetic expressions from postfix notation into infix notation. Give annotated parse trees for the inputs...

Construct a context-free grammar for roman numerals.

Show that all binary strings generated by the following grammar havevalues divisible by $3$. Hint. Use induction on the number of nodes in a parse tree. $$num\rightarrow ...

Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct. Arithmetic expressions in postfix notatio...

What language is generated by the following grammars? In each case justify your answer. $S\rightarrow 0S1 \mid 01$$S\rightarrow +SS \mid -SS \mid a$$S\rightarrow S(S)S \m...

Consider the context-free grammar$S\rightarrow SS+\mid SS^{\ast}\mid a$Show how the string $aa+a^{\ast}$ can be generated by this grammar.Construct a parse tree for this ...

For the block-structured code, assuming the usual static scoping of declarations, give the scope for each of the twelve declarations.{ int w,x,y,z; /* Block B1 */ { int x...

For the block-structured C code, indicate the values assigned to $w,x,y$ and $z$.int w,x,y,z; int i = 3; int j = 4; { int i = 5; w = i + j; } x = i + j; { int j = 6; i =...

For the block-structured C code, indicate the values assigned to $w, x, y$, and $z$. int w,x,y,z; int i = 4; int j = 5; { int j = 7; i = 6; w = i + j; } x = i + j; { int ...

Indicate which of the following terms:imperative declarative von Neumannobject-oriented functional third-generationfourth-generation scriptingapply to which of the follo...

It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but th...

Show that the language $\overline{L_A}\cup \overline{L_B}$ is a regular language if and only if it is the set of all strings over its alphabet;i.e., if and only if the in...

Let $L$ be the set of (codes for) context-free grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by co...

A Post tag system consists of a set of pairs of strings chosen from some finite alphabet $\Sigma$ and a start string. If $(w,x)$ is a pair, and $y$ is any string over $\S...

Suppose we limited $PCP$ to a one-symbol alphabet, say $\Sigma = \left\{0\right\}$. Would this restricted case of $PCP$ still be undecidable?

We showed that $PCP$ was undecidable, but we assumed that the alphabet $\Sigma$ could be arbitrary. Show that $PCP$ is undecidable even if we limit the alphabet to $\Sigm...

Tell whether each of the following instances of $PCP$ has a solution. Each is presented as two lists $A$ and $B$, and the $i^{th}$ strings on the two lists correspond for...

Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE.The set of all $TM$ codes for $TM's$ that halt on every input.The set of all $TM$ codes ...

Show that the following problems are not recursively enumerable:The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt.The set of pairs $(M_{1...

Show that the following questions are decidable:The set of codes for $TM's \ M$ such that when started with blank tape will eventually write some nonblank symbol on its t...

Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $...

Show that the language of codes for $TM's\ M$ that, when started with blank tape, eventually write a $1$ somewhere on the tape is undecidable.

The Big Computer Corp. has decided to bolster its sagging market share by manufacturing a high-tech version of the Turing machine called, $BWTM$ that is equipped with bel...

Show that the set of Turing-machine codes for TM's that accept all inputs that are palindromes (possibly along with some other inputs) is undecidable.

We have not discussed closure properties of the recursive languages or the RE languages other than our discussion of complementation in Section $9.2.2.$ Tell whether the ...

Let $L$ be recursively enumerable and let $\overline{L}$ be non-RE. Consider the language$L' = \left\{0w\mid w\ \text{is in}\ L \right\}$Can you say for certain whether $...