inductionprove```Here'sareallysimplelanguagewe'llcallP(forparentheses):1.Atoms:λinP.2.Moregenerally,ifuisinP,sois(u).Inotherwords,Pisthesetofallstringsoverthealphabet{(,)}inwhichparenthesesarepaired.Useinductionto

Question

induction prove```
Here's a really simple language we'll call P(for parentheses):
1.Atoms:λ in P.
2.More generally,if u is in P,so is (u).
In other words,P is the set of all strings over the alphabet{(,)}in which parentheses are paired.
Use induction to prove that,for every expression in P,the number of left parentheses is equal to the number of right parentheses.

Answer 1

对于P中一个元素u,定义k（u）为左括号数-右括号数
More generally,if u is in P,so is (u).
则对任何u,k（u）=0,
所以the number of left parentheses is equal to the number of right parentheses.
详细点,大概就是这样的
首先
对于Atoms:λ in P.so k（λ ）=0-0=0
假设对于u in P 有 k（u）=0
则对于（u）
k（（u））=k（u）+1-1=k（u）=0
用数学归纳法就知道所有P中的元素,都有k（u）=0
其实我也不一定保证就是对的,只是我是这样认为的.