Skip to main content
Computer Science

Return to Question

The title with TeX formatting was displayed incorrectly. Use plain text instead.
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91

Test whether $L= \{w\in\{a,b,c\}* \text{ | } |w|_a<|w|_b \text{words of less a's than b's or } |w|_a<|w|_c\text{,c's but not at the same time} \}$ is CFL or notcontext-free

I want to test whether $L= \{w\in\{a,b,c\}* \text{ | } |w|_a<|w|_b \text{ or } |w|_a<|w|_c\text{, but not at the same time} \}$$L= \{w\in\{a,b,c\}^* \mid |w|_a<|w|_b \text{ or } |w|_a<|w|_c,\text{ but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so.

The closest I have been to prove that it isn't a CFL is by seeing that the languages $L_1=\{a^nb^{n+1}c^n{ | }n>=0 \}$$L_1=\{a^nb^{n+1}c^n\mid n\ge0 \}$ and $L_2=\{a^nb^nc^{n+1}{ | }n>=0 \}$ $L_2=\{a^nb^nc^{n+1}\mid n\ge0 \}$, for example, are contained within it and are obviously not context-free, but that doesn't prove anything.

Any tips?

Test whether $L= \{w\in\{a,b,c\}* \text{ | } |w|_a<|w|_b \text{ or } |w|_a<|w|_c\text{, but not at the same time} \}$ is CFL or not

I want to test whether $L= \{w\in\{a,b,c\}* \text{ | } |w|_a<|w|_b \text{ or } |w|_a<|w|_c\text{, but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so.

The closest I have been to prove that it isn't a CFL is by seeing that the languages $L_1=\{a^nb^{n+1}c^n{ | }n>=0 \}$ and $L_2=\{a^nb^nc^{n+1}{ | }n>=0 \}$ , for example, are contained within it and are obviously not context-free, but that doesn't prove anything.

Any tips?

Test whether words of less a's than b's or c's but not at the same time is context-free

I want to test whether $L= \{w\in\{a,b,c\}^* \mid |w|_a<|w|_b \text{ or } |w|_a<|w|_c,\text{ but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so.

The closest I have been to prove that it isn't a CFL is by seeing that the languages $L_1=\{a^nb^{n+1}c^n\mid n\ge0 \}$ and $L_2=\{a^nb^nc^{n+1}\mid n\ge0 \}$, for example, are contained within it and are obviously not context-free, but that doesn't prove anything.

Any tips?

edited tags
Link
Lightsong
Lightsong
  • 239
  • 1
  • 8
Source Link
Lightsong
Lightsong
  • 239
  • 1
  • 8

Test whether $L= \{w\in\{a,b,c\}* \text{ | } |w|_a<|w|_b \text{ or } |w|_a<|w|_c\text{, but not at the same time} \}$ is CFL or not

I want to test whether $L= \{w\in\{a,b,c\}* \text{ | } |w|_a<|w|_b \text{ or } |w|_a<|w|_c\text{, but not at the same time} \}$ is CFL or not (I assume not), but I am struggling to do so.

The closest I have been to prove that it isn't a CFL is by seeing that the languages $L_1=\{a^nb^{n+1}c^n{ | }n>=0 \}$ and $L_2=\{a^nb^nc^{n+1}{ | }n>=0 \}$ , for example, are contained within it and are obviously not context-free, but that doesn't prove anything.

Any tips?