×
Samples Blogs Make Payment About Us Reviews 4.9/5 Order Now

Simulate Regular Expressions Through A Program In Haskell Assignment Solution

July 08, 2024
Dr. Chen Wang
Dr. Chen
🇦🇺 Australia
Haskell
Dr. Wang brings a wealth of academic expertise with a Ph.D. in Functional Programming Languages. With over 900 completed WAI assignments, she excels in guiding students through complex topics like monads, lazy evaluation, and type systems. Dr. Wang is also passionate about web security and enjoys helping students implement robust security measures in their WAI applications.
Key Topics
  • Instructions
  • Requirements and Specifications
Tip of the day
Use well-structured shaders to optimize rendering and ensure efficient resource management. Start with simple shapes, gradually adding complexity, and debug in small steps to identify errors easily.
News
An open-source framework that allows developers to create rich Python applications in the browser using HTML's interface, bridging the gap between web development and Python scripting.

Instructions

Objective

Write a Haskell assignment program that allows users to simulate regular expressions.

Requirements and Specifications

  • Define string containing regular expressions for the following languages over the alphabet {a,b,c}.

-- A. The language {"bc","cb","abc","acb"}

-- B. Strings that begin with 'a' and end with 'b' and do not contain 'c'

-- C. Strings in which 'c' occurs exactly once

-- D. Strings containing at least one 'a' and at least one 'b', where all 'a's occur earlier than any 'b'.

  • Define atmost such that atmost n r means r repeated up to n times. If n is 0 (or negative), atmost n r will be equivalent to eps (that is, repeating r zero times).
  • Define matchEmpty, which determines whether the language for a regular expression.

Screenshots of output

Simulate regular expressions in Haskell
Simulate regular expressions in Haskell 1

Source Code

{-# LANGUAGE TypeFamilies #-} module HW5 where -- Download Lec14.hs and Lec16.hs from Canvas and place them in the same directory as -- HW5.hs import Control.Applicative ((<|>)) import Lec14 (Parser, parse, pSym) import Lec16 pLetter :: Parser Char Char pLetter = pSym 'a' <|> pSym 'b' <|> pSym 'c' parseRE :: (Regular a, Symbol a ~ Char) => String -> Maybe a parseRE = parse (pRE pLetter) parseRE' :: String -> Maybe (RE Char) parseRE' = parseRE -- ***** -- 1. Define string containing regular expressions for the following languages over the -- alphabet {a,b,c}. -- -- Example. Strings containing 'a' two or more times example = "aa+" -- Note that you can use parseRE, recog, and upto to test your expressions. -- -- *HW5> parseRE' example -- Just (Compos (Sym 'a') (Repeat1 (Sym 'a'))) -- *HW5> upto 5 <$> parseRE example -- Just ["aa","aaa","aaaa","aaaaa"] -- *HW5> flip recog "aaa" <$> parseRE example -- Just True -- *HW5> flip recog "aaab" <$> parseRE example -- Just False -- A. The language {"bc","cb","abc","acb"} rega = "(a|e)(bc|cb)" -- B. Strings that begin with 'a' and end with 'b' and do not contain 'c' regb = "a(a|b)*b" -- C. Strings in which 'c' occurs exactly once regc = "(a|b)*c(a|b)*" -- D. Strings containing at least one 'a' and at least one 'b', where all 'a's occur -- earlier than any 'b'. regd = "(a|c)*a(a|c)*(b|c)*b(b|c)*" -- ***** -- 2. Define atmost such that atmost n r means r repeated up to n times. If n is 0 -- (or negative), atmost n r will be equivalent to eps (that is, repeating r zero -- times). -- -- *HW5> unL (atmost 3 (sym 'a' .&. sym 'b')) -- ["","ab","abab","ababab"] -- *HW5> unL (atmost 3 (sym 'a' .|. sym 'b')) -- ["","a","b","aa","ab","ba","bb","aaa","aab","aba","abb","baa","bab","bba","bbb"] -- *HW5> unL (atmost 0 (sym 'a')) -- [""] -- *HW5> unL (atmost 10 eps) -- [[]] -- *HW5> unL (atmost 10 none) -- [[]] atmost :: (Regular a) => Integer -> a -> a atmost n f = if n <= 0 then eps else eps .|. (f .&. atmost (n-1) f) -- ***** -- 3. Define matchEmpty, which determines whether the language for a regular expression -- includes the empty string. -- -- *HW5> matchEmpty <$> parseRE "aa|e" -- Just True -- *HW5> matchEmpty <$> parseRE "0" -- Just False -- *HW5> matchEmpty <$> parseRE "0*" -- Just True -- *HW5> matchEmpty <$> parseRE "a*b*" -- Just True -- *HW5> matchEmpty <$> parseRE "a*b*" -- Just True -- *HW5> matchEmpty <$> parseRE "a*b+" -- Just False matchEmpty :: RE symbol -> Bool matchEmpty (Sym _) = False matchEmpty Empty = True matchEmpty Never = False matchEmpty (Repeat0 _) = True matchEmpty (Repeat1 _) = False matchEmpty (Compos a b) = matchEmpty a && matchEmpty b matchEmpty (Choice a b) = matchEmpty a || matchEmpty b

Related Samples

Explore our free Haskell assignment samples to gain insights into functional programming concepts, recursive functions, and type systems. These samples showcase our expertise in Haskell programming, helping you understand its applications and complexities.