Hire Experts For Answers

Order Now#### Related Study Services

- Homework Answers
- Coursework writing help
- Term paper writing help
- Writing Help
- Paper Writing Help
- Research paper help
- Thesis Help
- Dissertation Help
- Case study writing service
- Capstone Project Writing Help
- Lab report Writing
- Take my online class
- Take my online exam
- Do my test for me
- Do my homework
- Do my math homework
- Online Assignment Help
- Do my assignment
- Essay Writing Help
- Write my college essay
- Write my essay for me

DESCRIPTION

Posted

Modified

Viewed
13

All details are in the coursework pdf.
Notes on answering this question:
- Pay attention to what kind of grammar I ask for (regular, or context
free, or some other type).
- For instance: if I ask for a regular grammar and you give me some other
kind of grammar, then you may lose marks!
- In particular, if your regular grammar contains a rule of the
form S⟶abγ or S⟶D or S⟶εD, then this is not a regular grammar and
your answer contains an error.
- Always clearly specify the start symbol.
- The alphabet (set of tokens) of a language cannot contain ε. ε is the
empty string, that is, an absence of tokens. If your answer contains
something of the form T={ε,…} (where T is supposed to be a set of tokens
for your language) — then your answer is probably wrong and you’re
probably losing marks.
Some of you have not met set notation before, so here’s a quick tutorial:
- The language determined by the regex /a*/ is { aⁿ | n ∈ ℕ} or equivalently {
aⁿ | n ∈ {0,1,2,…} } or equivalently { aⁿ | n ≥ 0 }.
- The language determined by the regex /(a|b)?/ is { a, b, ε }.
- The language determined by the regex /a+b+/ is { aᵐbⁿ | m,n ≥ 1 } or
equivalently { aᵐbⁿ | m ≥ 1, n ≥ 1 } or equivalently { aᵐbⁿ | m,n ∈ {1,2,3,…} }.
- The language determined by the English description “any nonzero digit” is
{ 1, 2, 3, 4, 5, 6, 7, 8, 9} or equivalently { 1, 2, … , 9} or equivalently { n | 9 ≥
n ≥ 1 } or equivalently { n | 0 < n ≤ 9 }.

Attachments

Part II: Grammars
Submission: On Canvas, under Assignments
Deadline: Week 5, Thurs 16th Feb 2023
Notes on answering this question:
- Pay attention to what kind of grammar I ask for (regular, or context
free, or some other type).
- For instance: if I ask for a regular grammar and you give me some other
kind of grammar, then you may lose marks!
- In particular, if your regular grammar contains a rule of the
form S⟶abγ or S⟶D or S⟶εD, then this is not a regular grammar and
your answer contains an error.
- Always clearly specify the start symbol.
- The alphabet (set of tokens) of a language cannot contain ε. ε is the
empty string, that is, an absence of tokens. If your answer contains
something of the form T={ε,…} (where T is supposed to be a set of tokens
for your language) — then your answer is probably wrong and you’re
probably losing marks.
Some of you have not met set notation before, so here’s a quick tutorial:
- The language determined by the regex /a*/ is { aⁿ | n ∈ ℕ} or equivalently {
aⁿ | n ∈ {0,1,2,…} } or equivalently { aⁿ | n ≥ 0 }.
- The language determined by the regex /(a|b)?/ is { a, b, ε }.
- The language determined by the regex /a+b+/ is { aᵐbⁿ | m,n ≥ 1 } or
equivalently { aᵐbⁿ | m ≥ 1, n ≥ 1 } or equivalently { aᵐbⁿ | m,n ∈ {1,2,3,…} }.
- The language determined by the English description “any nonzero digit” is
{ 1, 2, 3, 4, 5, 6, 7, 8, 9} or equivalently { 1, 2, … , 9} or equivalently { n | 9 ≥
n ≥ 1 } or equivalently { n | 0 < n ≤ 9 }.
Now on to the questions:
1. Write the language determined by the regex /a*b*/
2. Write a regular grammar to generate the language determined by the
regex /a*b*/
3. Write the language determined by the regex /(ab)*/
4. Write a regular grammar to generate the language determined by the
regex /(ab)*/
5. Write the language determined by /Whiske?y/. The alphabet is
{W,h,i,s,k,e,y} (W is a terminal symbol here).
6. Write a regular grammar to generate the language matched by /Whiske?y/
7. Write a regular grammar to generate decimal numbers; the relevant
regex is /[1-9][0-9]*(\.[0-9]*[1-9])?/.
You may find it useful to use notation resembling D ::= 0 | 1 | … | 9 to
denote an set of ten production rules.
8. Give a context free grammar for the language L = { aⁿ bⁿ | n ∈ ℕ}.
9. Give a context free grammar for the set of properly bracketed sentences
over alphabet { 0 , ( , ) }. So 0 and ((0)) are fine, and 00 and 0) are not
fine.
10. Write a context free grammar to generate possibly bracketed
expressions of arithmetic with + and * and single digit numbers.
So 0 and (0) and 0+1+2 and (0+9) are fine, and (0+)1 and 12 are not fine.
11. Give a grammar for palindromes over the alphabet { a , b }.
12. A parity-sequence is a sequence consisting of 0s and 1s that has an
even number of ones. Give a grammar for parity-sequences.
13. Write a grammar for the set of numbers divisible by 4 (base 10; so
the alphabet is [0-9]). You might like to read this page on divisibility
testing, first. You may use dots notation to represent a sequence, as in
for example the sequence Z3,Z6,Z9,…,Z999 to mean “Z followed by some
number divisible by three and strictly between 0 and 1000”.
14. Write a grammar for the set of numbers divisible by 3 (base 10; so
the alphabet is [0-9]). So for example 0, 003, and 120 should be in your
language, and 1, 2, and 5 should not
15. (Unmarked) Write a grammar for the set of numbers divisible by 11
(base 10; so the alphabet is [0-9]).
More on Grammars ….
16. State which of the following production rules are left-regular, right-
regular, left-recursive, right-recursive, context-free (or more than one, or
none, of these):
1. Thsi ⟶ This (a rewrite auto-applied by Microsoft Word).
2. Sentence ⟶ Subject Verb Object. (Here Sentence, Subject, Verb, and
Object are non-terminal symbols.)
3. X ⟶ Xa.
4. X ⟶ XaX.
17. What is the object language generated by X⟶Xa (see Lecture 2)?
Explain your answer.
18. Construct context-free grammars that generate the following
languages:
1. (ab|ba)∗,
2. {(ab)n an| n≥1},
3. {w∈{a,b}∗ | w is a palindrome}
4. {w∈{a,b}∗ | w contains exactly two bs and any number of as }
5. {an bm| 0≤n≤m≤2n}
19. Consider the grammar G=({S,A,B},{a,b},P,S) with productions
S ⟶ SAB | ε
A ⟶ aA | ε
B ⟶ Bb | ε
1. Give a leftmost derivation for aababba.
2. Draw the derivation tree corresponding to your derivation.
20. State with proof whether the following grammars are ambiguous or
unambiguous:
1. G=({S},{a,b},P,S) with productions S ⟶ aSa | aSbSa | ε
2. G=({S},{a,b},P,S) with productions S ⟶ aaSb | abSbS | ε
21. Rewrite the following grammar to eliminate left-recursion:
exp ⟶ exp + term ∣ exp – term ∣ term
22. Write a grammar to parse arithmetic expressions (with + and ×) on
integers (such as 0, 42, −1). This is a little harder than it first sounds
because you will need to write a grammar to generate correctly-formatted
positive and negative numbers; a grammar that generates −01 is
unacceptable. You may use dots notation to indicate obvious replication
of rules, as in “D⟶0∣⋯∣9”, without comment.
(Note that a parser is not an evaluator. This question is not asking you to
write an evaluator. Also note that the grammar only needs to be
unambiguous if the question asks you to provide an unambiguous
grammar.)
23. Write two distinct parse trees for 2+3∗4 and explain in intuitive terms
the significance of the two different parses to their denotation.
Part III: DFAs and NFAs
Submission: On Canvas, under Assignments
Deadline: Week 7, Fri 3rd March 2023
You may find draw.io useful for drawing automata. If you know of a similar
and better tool, please let me know. You can insert images from
https://automatonsimuator.com too as long as the edge annotations are
clearly shown (note sometimes they are difficult to read).
1. By writing a regular expression or a grammar, describe the language
accepted by the DFA
2. By writing a regular expression or a grammar, describe the language
accepted by the DFA
3. Construct NFAs (possibly with ϵ-moves) to recognise the languages on
alphabet {a,b} such that:
1. L={w∈{a,b}∗ | w contains at most two a’s}.
So ϵ and aa and bbbbabba are in L and aaa is not.
2. L={w∈{a,b}∗ | w contains an even number of occurrences of ab as a
subword }. So ϵ and a and b and abab and abaaba and baaabab are
in L, but ab and ababab and abaabab are not.
3. L={w∈{a,b}∗ | the first and the last letter of w are identical }
4. By writing a regular expression or a grammar, describe the language
accepted by the NFA
5. By writing a regular expression or a grammar, describe the language
accepted by the NFA
6. (Unmarked) Use the powerset construction (see Lecture 5) to construct
a DFA that recognises the same language as the following NFA:
7. (Hard) Let L be the language recognised by the NFA
1. Construct a context-free grammar G that generates language L (a
regular grammar is also fine, since every regular grammar is context-
free).
2. State with proof whether G is ambiguous or unambiguous.
8. (Unmarked) Let G=({S,A,B},{a,b},P,S) be the context-free grammar with
productions:
S ⟶ aAbS | bBaS | ε
A ⟶ aAbA | ε
B ⟶ bBaB | ε
Give a short and intuitive English description of the language determined
by G (such a description does exist).
On PDAs
In the questions below, assume the alphabet is {a,b}. Your answer must
state the acceptance mode used. In the questions below, the
word describe means draw a precise picture of in the style I used in
lectures or in the style of this webpage or this pdf, or just search the
Internet for how to draw a PDA.
9. Describe a pushdown automaton that recognises {ambnam∣m,n≥0}.
10. Assume m,n≥0. Describe a DFA that recognises { ambnam }.
Explain why this question is different from the previous question.
11. Describe a pushdown automaton that recognises {amb2n∣m,n≥0}.
12. Describe a pushdown automaton that recognises {am bn∣m>n>0}.
13. Describe a pushdown automaton that recognises {w∣#aw = #bw},
where #aw is the number of as appearing in w and #b w is the number
of bs appearing in w.
14. Describe a pushdown automaton that recognises {w∣#aw = 2#bw }.
15. Describe a pushdown automaton that recognises {w∣#aw ≠ #bw}

Explanations and Answers
1

0

Answer:
All details are in the coursework pdf.
Notes on answering this question:
- Pay attention to what kind of grammar I ask for (regular, or context
free, or some other type).
- For instance: if I ask for a regular grammar and you give me some other
kind of grammar, then you may lose marks!
- In particular, if your regular grammar contains a rule of the
form S⟶abγ or S⟶D or S⟶εD, then this is not a regular grammar and
your answer contains an error.
- Always clearly specify the start symbol.
- The alphabet (set of tokens) of a language cannot contain ε. ε is the
empty string, that is, an absence of tokens. If your answer contains
something of the form T={ε,…} (where T is supposed to be a set of tokens
for your language) — then your answer is probably wrong and you’re
probably losing marks.
Answer. Please find attached the completed work. Let me know if you need anything. I will be here to assist.
Best Regards.

$0.00

From 0 reviews

Profsimon

answered

#### Answer Reviews

(0)
This answer has not been reviewed yet. Like to add yours?

### Post your Answer - free or at a fee

**NB: **Post a homework question for free and get answers - free or paid homework help.

Get answers to: Language Processor (Regex, Grammar And Dfas And Nfas ) or similar questions only at Tutlance.

Related Questions

- To Do My Homework On Artificial Intelligence
- To Do My Homework On Artificial Intelligence
- To Do My Homework On Artificial Intelligence
- To Do My Homework On Artificial Intelligence
- Looking For Someone To Take My Security+ Test
- Computer Systems Architecture And Information System Analysis
- Ntw216 System Design- Creating A System For A Company And Present It
- Cs Homework Urgent Please Help
- Developing A Rest Api For Exam
- Cryptography - Rsa, Wep, Scyther
- Automata Theory 4 Assignments, Pushdown Automata, Probabilistic Acceptor
- Computer Science Project Report
- Recursion In Hmmm Assembly Language
- Can You Do My Network Infrastructure And You Will Need Visio
- Digital Transformation In The Financial Industry Of Kazakhstan
- Software Engineering Principles Assignment
- Software Engineering Principles Assignment
- Fix A Completed Computer Network Compression Detection Project In C
- Please Could Someone Help Me With This Problem
- Show That The 3 Round Fiestal Network Is Not A Prf. (Pseudorandom Function)
- Fix A Completed Computer Network Compression Detection Project In C
- Fix A Completed Computer Network Compression Detection Project In C
- Tacacs + Information Security
- Basic Analysis Of 3 Pcap Files
- Tacacs + Information Security
- Algorithms And Data Structures Final Exam
- Algorithms And Data Structures Final Exam
- Algorithms And Data Structures Final Exam
- Algorithms And Data Structures Quiz 2
- Algorithms And Data Structures Quiz 2
- Assignment Help In Python And Pyopengl
- Computer Network Programming Project In C - End-To-End Detection Of Network Compression
- Computer Network Programming Project In C - End-To-End Detection Of Network Compression
- Computer Network Programming Project In C - End-To-End Detection Of Network Compression
- Computer Network Programming Project In C - End-To-End Detection Of Network Compression
- Cybersecurity Topic Infographic Poster
- Wireshark Paper And Presentation
- Computer Science, Assembly, Pep/8
- It B Or Better. Excel And Word. Clippings Needed
- Python, Flask, Mysql, Bcrypt, Regex
- Essentials Of Computer Architecture Homework
- Algorithms And Data Structures Quiz 2
- Algorithms And Data Structures Quiz 2
- Algorithms And Data Structures Quiz 2
- Algorithms And Data Structures Quiz 2
- Iterative Closest Point And A Horn's Method Algorithm Together. State Esimation By Particle Filtering On A Lie Group.
- Iterative Closest Point And A Horn's Method Algorithm Together. State Esimation By Particle Filtering On A Lie Group.
- Algorithms And Data Structures Quiz 2
- Algorithms And Data Structures Quiz 2
- Algorithms And Data Structures Quiz 2