Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/372603530299072512
corrected spelling: occurrence --> occurrence. Edited math and changed L_1 to L
Source Link
Luke Mathieson
  • 18.3k
  • 4
  • 59
  • 87

I need help with deciding if L$L$ is context-free.

$$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurrence of $c$, we push the $c$:s onto the stack. But we can't make difference between $d^q$ and $d^t$, so comparing $s < t$ is impossible when popping the $d$:s.

Hence $L$ is not Context-Free.

Is my reasoning right ?

I need help with deciding if L is context-free.

$$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurrence of $c$, we push the $c$:s onto the stack. But we can't make difference between $d^q$ and $d^t$, so comparing $s < t$ is impossible when popping the $d$:s.

Hence $L$ is not Context-Free.

Is my reasoning right ?

I need help with deciding if $L$ is context-free.

$$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurrence of $c$, we push the $c$:s onto the stack. But we can't make difference between $d^q$ and $d^t$, so comparing $s < t$ is impossible when popping the $d$:s.

Hence $L$ is not Context-Free.

Is my reasoning right ?

corrected spelling: occurrence --> occurrence. Edited math and changed L_1 to L
Source Link

I need help with deciding if L1L is context-free.

$$L_1 = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$$$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L_1 = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$$$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurenceoccurrence of c$c$, we push the c$c$:s onto the stack. But we can't make difference between d^q$d^q$ and d^t$d^t$, so comparing s < t$s < t$ is impossible when popping the d$d$:s.

Hence L1$L$ is not Context-Free.

Is my reasoning right ?

I need help with deciding if L1 is context-free.

$$L_1 = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L_1 = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurence of c, we push the c:s onto the stack. But we can't make difference between d^q and d^t, so comparing s < t is impossible when popping the d:s.

Hence L1 is not Context-Free.

Is my reasoning right ?

I need help with deciding if L is context-free.

$$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurrence of $c$, we push the $c$:s onto the stack. But we can't make difference between $d^q$ and $d^t$, so comparing $s < t$ is impossible when popping the $d$:s.

Hence $L$ is not Context-Free.

Is my reasoning right ?

Source Link
mrjasmin
  • 586
  • 1
  • 5
  • 12

Deciding if language is Context-Free

I need help with deciding if L1 is context-free.

$$L_1 = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L_1 = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurence of c, we push the c:s onto the stack. But we can't make difference between d^q and d^t, so comparing s < t is impossible when popping the d:s.

Hence L1 is not Context-Free.

Is my reasoning right ?