Register

CMI2022-B: 2

• edited by
219 views
0 votes
0 votes

Consider the language $\text{L}$ over the alphabet $\left \{ a, b \right \}$ given below.

$$\text{L}= \{ w \mid w  \;\text{has equal number of $a$’s and $b$’s, and there are no adjacent $a$’s.}\}$$

For instance, the words $abba, abab$ are in language but not $bab$ and $baab$.

  1. Prove that $\text{L}$ does not contain any word that starts and ends with $a$ $b$.
  2. Give a context-free grammar for $\text{L}$.
• edited by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
0 answers
1
admin asked Jul 22, 2022
345 views
CMI2022-B: 1
A Muller automaton is defined as a tuple $\text{M} = (\text{Q}, \text{I}, \Sigma, \rightarrow, \text{T})$ where: $\text{Q}$ is a finite set of states; $\text{I} \subseteq \text{Q}$ is the set of initial states; $\Sigma$ ... $a^{\ast}?$
A Muller automaton is defined as a tuple $\text{M} = (\text{Q}, \text{I}, \Sigma, \rightarrow, \text{T})$ where:$\text{Q}$ is a finite set of states;$\text{I} \subseteq \...
User Avatar
0 votes
0 votes
0 answers
3
admin asked Jul 22, 2022
278 views
CMI2022-B: 5
For any set $\text{S}$ of natural numbers, we say that a relation $\text{R} \subseteq \text{S} \times \text{S}$ is a $2$-spanner of $\text{S}$ if it satisfies the following conditions: $\left ( i, j \right ) \in R \Rightarrow i < j$ ... any set $\text{S}$ of size $2^{k} - 1$ (for $k > 2)$ has a $2$-spanner of size $(k - 2) 2^{k} + 2$.
For any set $\text{S}$ of natural numbers, we say that a relation $\text{R} \subseteq \text{S} \times \text{S}$ is a $2$-spanner of $\text{S}$ if it satisfies the followi...
User Avatar
Link Copied!