• <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)-大理旅游
      油炸竹蟲
      油炸竹蟲
      酸筍煮魚(雞)
      酸筍煮魚(雞)
      竹筒飯
      竹筒飯
      香茅草烤魚
      香茅草烤魚
      檸檬烤魚
      檸檬烤魚
      昆明西山國家級風景名勝區
      昆明西山國家級風景名勝區
      昆明旅游索道攻略
      昆明旅游索道攻略
    • NBA直播 短信驗證碼平臺 幣安官網下載 歐冠直播 WPS下載

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

      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>
        主站蜘蛛池模板: 伊人情人综合网| 久久精品国产亚洲精品| 天天做天天添婷婷我也去| 老子影院午夜伦手机在线看| 免费国产成人手机在线观看 | 黄色小视频app下载| 免费精品国产日韩热久久| 天天射天天干天天| 欧美日韩第一区| 一级做a爱一区| 伊人色在线视频| 国产精品爆乳在线播放第一人称| 欧美巨大另类极品videosbest| 91精品国产人成网站| 久久久久亚洲AV无码专区体验 | 国产精品色拉拉免费看| 人体大胆做受大胆视频一| 国产精品另类激情久久久免费 | 真实子伦视频不卡| 中国老熟妇xxxxx| 国产乱码卡一卡2卡三卡四| 日韩精品久久无码人妻中文字幕| 亚洲天堂成人网| 夜色资源网站www| 日韩精品久久无码中文字幕| 91精品国产综合久久久久久| 国产丰满老熟女重口对白| 果冻传媒和91制片厂| avtt2015天堂网| 久久亚洲色www成人欧美| 日韩一卡2卡3卡4卡| 日本a免费观看| 三上悠亚破解版| 女人脱裤子让男生桶的免费视频| 一本一本久久a久久综合精品| 国产乱码一区二区三区四| 青青青青久久久久国产的| 久久国产精品张柏芝| 日本在线视频www色| 亚洲精品中文字幕无码蜜桃| 国产精品爽爽va在线观看无码|