• <button id="ecio8"></button>
  • <li id="ecio8"></li>
    <s id="ecio8"></s>
    <dl id="ecio8"></dl>
    <center id="ecio8"><noscript id="ecio8"></noscript></center>
    • <table id="ecio8"><source id="ecio8"></source></table>
      <bdo id="ecio8"></bdo>
    • <s id="ecio8"></s>

      CS 161代做、Java/Python程序代寫

      時間:2024-04-25  來源:  作者: 我要糾錯



      CS 161, Spring 2024: Homework 2
      Homework 2: NFAs and Regular Expressions
      0. (Ungraded exercise) We rushed/didn’t get to the exercises at the end of worksheet 3
      (copied below for convenience). Make sure you understand what is wrong with these
      proofs.
      (a) Here is a false statement with a bad proof. What is wrong with the proof?
      Theorem (Not actually true). Every binary language is regular.
      Proof. Let A be any language. Here is a DFA M:
      M q0
      0,1
      Note that any string in A is accepted by this DFA. Thus, this DFA recognizes A,
      so A is regular.
      (b) Here is a false statement with a bad proof. What is wrong with the proof?
      Theorem (Not actually true). The language A = {00, 11} is not regular.
      Proof. Here is a DFA M:
      M q0 q1
      0 1
      1
      0
      The string 11, which is in A, is not accepted by this DFA. Thus, the DFA M does
      not recognize A, so A is not regular.
      1. (10 points) Let L be the language of binary strings with at least two 0s or at least
      three 1s.
      (a) (5 points) Draw a state diagram for an NFA that recognizes L.
      (b) (5 points) Recall that an NFA is a 5-tuple N = (Q, Σ, δ, q0, F) for finite set of states
      Q, finite set of alphabet characters Σ, transition function δ : Q × Σε → P(Q),
      start state q0 ∈ Q, and accept states F ⊂ Q. Describe your NFA as a 5-tuple.
      2. (10 points) Prove the following theorem by generalizing the construction from Worksheet 6.
      Theorem. The set of regular languages are closed under concatenation.
      (c) Sara Krehbiel, Ray Li 1
      CS 161, Spring 2024: Homework 2
      That is, prove that, for any two regular languages A and B, the language A ◦ B =
      {ab : a ∈ A : b ∈ B} is regular.
      3. (5 points) Consider the NFA N = ({1, 2, 3}, {0, 1}, δ, 1, {3}) with δ as depicted below (this is the same one from Quiz 6). Give a regular expression for the language
      recognized by this NFA.
      N 1 2 3
      ε
      1
      0
      1 0
      4. (10 points) Find an NFA that recognizes the language of (0◦1)∗ ◦(0∪1) (the alphabet is
      Σ = {0, 1}). Include both a state diagram and a formal specification of your automaton
      as a 5-tuple.
      5. (10 points) Let A be the language of strings over Σ = {0, 1} from the first day of class:
      A = {1
      a01b01a+b
      : a, b ≥ 0}. Prove that A is not regular. (An informal interpretation
      of this result is: DFAs cannot add in unary) Hint: 1
      6. (15 points) We see in class on 4/15 how to convert any k-state NFA into an equivalent
      2
      k
      -state DFA. This problem shows that this exponential blowup in the number of states
      is necessary. Let A ⊂ {0, 1}
      ∗ be the set of all strings (of length at least 101) that have
      a 0 exactly 100 places from the right hand end. That is
      A = {w : |w| ≥ 101, w|w|−100 = 0}. (1)
      (a) (5 points) Draw the state diagram for an NFA with 101102 states that recognizes
      A. (You can use “· · · ” and don’t have to draw all 101102 states, as long as it’s
      clear what the states/transitions would be in the omitted states) [Ray: Update: I
      think you need 102 states. If you have 103 or 104 states, that’s fine.]
      (b) (10 points) Show that no DFA on less than 2100 states can recognize A. Hint:2
      1
      In this class, we learn several methods for proving a language A is regular: constructing a DFA recognizing A, constructing an NFA recognizing A, finding a regular expression for A. However, we only learn
      one method for proving a language is not regular. What is it?
      2Give a proof by contradiction and assume such a DFA exists. Apply pigeonhole to all 2100 strings of
      length 100 to get two strings x and y of length 100 that end up at the same state after digesting. Derive a
      contradiction by considering the strings xz and yz for some carefully chosen string z.
      (c) Sara Krehbiel, Ray Li 2

      請加QQ:99515681  郵箱:99515681@qq.com   WX:codinghelp

      標簽:

      掃一掃在手機打開當前頁
    • 上一篇:COMP2013代做、代寫Data Structures and Algorithms
    • 下一篇:代做COMP3211、Python/Java程序代寫
    • 無相關信息
      昆明生活資訊

      昆明圖文信息
      蝴蝶泉(4A)-大理旅游
      蝴蝶泉(4A)-大理旅游
      油炸竹蟲
      油炸竹蟲
      酸筍煮魚(雞)
      酸筍煮魚(雞)
      竹筒飯
      竹筒飯
      香茅草烤魚
      香茅草烤魚
      檸檬烤魚
      檸檬烤魚
      昆明西山國家級風景名勝區
      昆明西山國家級風景名勝區
      昆明旅游索道攻略
      昆明旅游索道攻略
    • 高仿包包訂製

      關于我們 | 打賞支持 | 廣告服務 | 聯系我們 | 網站地圖 | 免責聲明 | 幫助中心 | 友情鏈接 |

      Copyright © 2025 kmw.cc Inc. All Rights Reserved. 昆明網 版權所有
      ICP備06013414號-3 公安備 42010502001045

      欧美成人免费全部观看天天性色,欧美日韩视频一区三区二区,欧洲美女与动性zozozo,久久久国产99久久国产一
    • <button id="ecio8"></button>
    • <li id="ecio8"></li>
      <s id="ecio8"></s>
      <dl id="ecio8"></dl>
      <center id="ecio8"><noscript id="ecio8"></noscript></center>
      • <table id="ecio8"><source id="ecio8"></source></table>
        <bdo id="ecio8"></bdo>
      • <s id="ecio8"></s>
        主站蜘蛛池模板: 100款夜间禁用b站软件下载| 亚洲快播电影网| av一本久道久久综合久久鬼色| 美女18毛片免费视频| 探花国产精品三级在线播放| 国产免费无码一区二区视频| 久久影院最新消息| 青苹果乐园影视免费观看电视剧hd | 欧美亚洲国产一区二区三区| 国产精品成人免费视频电影| 亚洲国产精品网| 你懂的国产高清在线播放视频| 欧美亚洲国产精品久久高清| 国产精品午夜小视频观看 | 精品无码人妻夜人多侵犯18| 性欧美大战久久久久久久| 免费黄色大片网站| a级毛片免费高清视频| 漂亮人妻被黑人久久精品| 校花哭着扒开屁股浣肠于柔| 国产日产欧美精品| 久久无码人妻精品一区二区三区 | 精品香蕉一区二区三区| 少妇人妻偷人精品视蜜桃| 国产成人综合色视频精品| 久久毛片免费看一区二区三区 | 久久精品视频6| 蜜桃成熟时无删减手机在线观看 | 韩国特黄特色a大片免费| 播播开心激情网| 八戒八戒www观看在线| 99久久精彩视频| 欧美一级在线观看视频| 国产国产人免费视频成69堂| 中文字幕免费播放| 福利视频一区二区三区| 国产超碰人人爽人人做人人添| 五月婷婷色丁香| 美女的大胸又黄又www又爽| 天天干在线观看| 亚洲制服丝袜第一页|