retagged by
536 views
7 votes
7 votes

For a string $x=x_1 \cdots x_n \in \Sigma^*$, where $\Sigma$ is any alphabet and $x_1, \ldots, x_n \in \Sigma$, we write $x^{\uparrow m}=x^m$ (that is, the usual power of strings) and $x^{\downarrow m}=x_1^m \cdots x_n^m$.

For empty string $x=\varepsilon, \varepsilon^{\uparrow m} =\varepsilon ; \varepsilon^{\downarrow m} =\varepsilon $.

Which of the following languages cannot be described as "context-free but not regular"? (Assume $\Sigma=\{a, b, c\})$

  1. $\left\{x^{\downarrow 2} \mid x \in \Sigma^*\right\} $
  2. $\left\{(a b c)^{\uparrow n} \mid n \geq 0\right\}$
  3. $\left\{x^{\uparrow 2} \mid x \in \Sigma^*\right\}$
  4. $\left\{(a b c)^{\downarrow n} \mid n \geq 0\right\}$
retagged by

1 Answer

5 votes
5 votes
A, B are regular. C,D are Non-Context-Free.

$\text{A}=(a a+b b+c c)^*$

$\mathrm{B}=(\mathrm{abc})^*$

$\mathrm{C}=\left\{\mathrm{ww} \mid \mathrm{w} \in \Sigma^{\ast}\right\}$

$\mathrm{D}=\left\{a^nb^n c^n \mid n \geq 0\right\}$
edited by
Answer:

Related questions

720
views
1 answers
6 votes
GO Classes asked Jan 28
720 views
Which of the following statements is/are false?If a context-free grammar $\mathrm{G}$ is in Chomsky's normal form, then $\mathrm{G}$ ... $100$-state DFA that accepts $\mathrm{L}$.
700
views
1 answers
8 votes
GO Classes asked Jan 28
700 views
Consider a pushdown automaton (PDA) with two control states $Q=\{q 1, q 2\}$, start state $q 1$, input alphabet $\Sigma=\{a, b\}$, stack ... stack.)The number of strings of length $21$ accepted by the above pushdown automaton is _________.
651
views
1 answers
3 votes
GO Classes asked Jan 28
651 views
Consider the syntax-directed translation given by the following grammar and semantic rules. Here, $S$ is the only non-terminal and $\Sigma=\{0,1,2\}$ is a ... The value computed by the translation scheme for the input string $201$ is $20.$
457
views
1 answers
4 votes
GO Classes asked Jan 28
457 views
Consider the following grammar$\begin{aligned}& A \rightarrow B B \\& B \rightarrow b\end{aligned}$Suppose we draw an $\operatorname{LR}(0)$ ... state with $2$ incoming transitionsThere is exactly one state with $3$ outgoing transitions