User Lightsong

3 votes

2 answers

477 views

Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$

asked Jan 28, 2021 at 14:25

2 votes

4 answers

197 views

If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

asked Jan 13, 2021 at 18:11

1 vote

1 answer

53 views

Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$

asked Jan 16, 2021 at 12:52

1 vote

1 answer

64 views

Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular

asked Feb 3, 2021 at 12:52

1 vote

1 answer

65 views

Trying to find two CFGs for the following languages

asked Dec 13, 2020 at 18:46

1 vote

1 answer

152 views

Some questions regarding methods for solving pushdown automata problems

asked Dec 30, 2020 at 18:49

1 vote

1 answer

57 views

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

asked Aug 30, 2021 at 14:18

1 vote

0 answers

67 views

Combine Las Vegas and Montecarlo probabilistic algorithms to improve chance of finding correct answer

asked Nov 13, 2022 at 19:44

1 vote

2 answers

197 views

Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

asked Jan 10, 2021 at 18:49

0 votes

1 answer

78 views

Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$

asked Jan 4, 2021 at 19:50

0 votes

1 answer

2k views

Understanding the union of an undecidable language with a finite or decidable language

asked Jan 8, 2021 at 10:34

0 votes

1 answer

106 views

Interesting Speedup & Amdahl's law problem

asked Feb 27, 2021 at 16:04

Stack Exchange Network

12 Questions

Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$

If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$

Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular

Trying to find two CFGs for the following languages

Some questions regarding methods for solving pushdown automata problems

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

Combine Las Vegas and Montecarlo probabilistic algorithms to improve chance of finding correct answer

Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$

Understanding the union of an undecidable language with a finite or decidable language

Interesting Speedup & Amdahl's law problem